E - Work or Rest

Contest Duration: 2023-01-15(Sun) 12:00 - 2023-01-15(Sun) 13:40 (local time) (100 minutes) Back to Home

E - Work or Rest Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $500$ 点

問題文

高橋君が住む世界の一週間は $N$ 日からなります。
一週間は曜日 $1,2,\dots,N$ と進んでいき、曜日 $N$ が終わると次の週の曜日 $1$ が始まります。

ABC 国の国王である高橋君は、各曜日に「平日」「休日」のどちらかを割り当てます。この割り当ては毎週同じでなければなりません。また、少なくとも $1$ つの曜日を「休日」に割り当てなければなりません。

この条件の下で、曜日 $i$ の生産量は長さ $N$ の数列 $A$ を用いて以下のように定義されます。

曜日 $i$ が「休日」である場合は $0$
曜日 $i$ が「平日」のとき、直前の休日が $x$ 日前、直後の休日が $y$ 日後である場合は $A_{\min(x,y)}$
- 割り当ては毎週繰り返されるため、直前 / 直後の「休日」が当日とは別の週に属する可能性があることに注意してください。詳しくはサンプルを参照してください。

上手く割り当てを決めたときの一週間当たりの生産量の最大値を答えてください。
但し、一週間当たりの生産量とは曜日 $1,2,\dots,N$ の生産量の総和を指します。

制約

入力はすべて整数
$1 \le N \le 5000$
$1 \le A_i \le 10^9$

入力

入力は以下の形式で標準入力から与えられる。

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

出力

答えを整数として出力せよ。

入力例 1Copy

Copy

7
10 10 1 1 1 1 1

出力例 1Copy

Copy

例えば曜日 $2,4$ を「休日」、残りを「平日」に割り当てることで、以下のように一週間当たりの生産量 $50$ を達成できます。

曜日 $1$ ... $x=4,y=1$ なので、この曜日の生産量は $A_1 = 10$ である。
曜日 $2$ ... 「休日」であるので、この曜日の生産量は $0$ である。
曜日 $3$ ... $x=1,y=1$ なので、この曜日の生産量は $A_1 = 10$ である。
曜日 $4$ ... 「休日」であるので、この曜日の生産量は $0$ である。
曜日 $5$ ... $x=1,y=4$ なので、この曜日の生産量は $A_1 = 10$ である。
曜日 $6$ ... $x=2,y=3$ なので、この曜日の生産量は $A_2 = 10$ である。
曜日 $7$ ... $x=3,y=2$ なので、この曜日の生産量は $A_2 = 10$ である。

一週間当たりの生産量を $51$ 以上にすることはできません。

入力例 2Copy

Copy

10
200000000 500000000 1000000000 800000000 100000000 80000000 600000 900000000 1 20

出力例 2Copy

Copy

5100000000

入力例 3Copy

Copy

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

出力例 3Copy

Copy

Score : $500$ points

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 1Copy

Copy

7
10 10 1 1 1 1 1

Sample Output 1Copy

Copy

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 2Copy

Copy

10
200000000 500000000 1000000000 800000000 100000000 80000000 600000 900000000 1 20

Sample Output 2Copy

Copy

5100000000

Sample Input 3Copy

Copy

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

Sample Output 3Copy

Copy