Score : $500$ points

问题描述

在高桥生活的世界中，一周有 $N$ 天。

作为AtCoder王国的国王，高桥将每周的每一天标记为“工作日”或“假日”。这种标记对于所有周都应保持一致。至少有一天应被标记为“假日”。

在这种条件下，一周中第 $i$ 天的工作效率由长度为 $N$ 的序列 $A$ 如下定义：

• 如果第 $i$ 天是“假日”，其工作效率为 $0$；
• 如果第 $i$ 天是“工作日”，若上一个假日在其前 $x$ 天，下一个假日在其后 $y$ 天，则其工作效率为 $A_{\min(x,y)}$。
  • 注意，由于周期性的标记安排，上一个/下一个假日可能属于不同周。具体细节请参见示例部分。

当最优地选择标记时，求出每周最大工作效率。 这里，每周的工作效率指一周中第 $1$、$2$、$\dots$、$N$ 天的工作效率之和。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

In the world where Takahashi lives, a week has $N$ days.

Takahashi, the king of the Kingdom of AtCoder, assigns "weekday" or "holiday" to each day of week. The assignments should be the same for all weeks. At least one day of week should be assigned "holiday".

Under such conditions, the productivity of the $i$-th day of week is defined by a sequence $A$ of length $N$ as follows:

• if the $i$-th day of week is "holiday", its productivity is $0$;
• if the $i$-th day of week is "weekday", its productivity is $A_{\min(x,y)}$, if the last holiday is $x$ days before and the next one is $y$ days after.
  • Note that the last/next holiday may belong to a different week due to the periodic assignments. For details, see the Samples.

Find the maximum productivity per week when the assignments are chosen optimally.
Here, the productivity per week refers to the sum of the productivities of the $1$-st, $2$-nd, $\dots$, and $N$-th day of week.

Constraints

• All values in the input are integers.
• $1 \le N \le 5000$
• $1 \le A_i \le 10^9$

Input

The input is given from Standard Input in the following format:

$N$

$A_1$ $A_2$ $\dots$ $A_N$

Output

Print the answer as an integer.

Sample Input 1

7
10 10 1 1 1 1 1

Sample Output 1

50

For example, we can assign "holiday" to the $2$-nd and $4$-th day of week and "weekday" to the rest to achieve a productivity of $50$ per week:

• the $1$-st day of week ... $x=4$ and $y=1$, so its productivity is $A_1 = 10$.
• the $2$-nd day of week ... it is holiday, so its productivity is $0$.
• the $3$-st day of week ... $x=1$ and $y=1$, so its productivity is $A_1 = 10$.
• the $4$-th day of week ... it is holiday, so its productivity is $0$.
• the $5$-th day of week ... $x=1$ and $y=4$, so its productivity is $A_1 = 10$.
• the $6$-th day of week ... $x=2$ and $y=3$, so its productivity is $A_2 = 10$.
• the $7$-th day of week ... $x=3$ and $y=2$, so its productivity is $A_2 = 10$.

It is impossible to make the productivity per week $51$ or greater.

Sample Input 2

10
200000000 500000000 1000000000 800000000 100000000 80000000 600000 900000000 1 20

Sample Output 2

5100000000

Sample Input 3

20
38 7719 21238 2437 8855 11797 8365 32285 10450 30612 5853 28100 1142 281 20537 15921 8945 26285 2997 14680

Sample Output 3

236980

update @ 2024/3/10 11:55:57