/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
無限に広がる池があり、数直線とみなせます。この池には N 個の蓮が浮かんでおり、それらは座標 0,1,2,....N-2,N-1 にあります。
あなたは、最初座標0 の蓮の上にいます。あなたは、以下の手順に従ってゲームを行うことにしました。
-
1.正の整数 A,B を決める。得点ははじめ 0 である。
-
2.現在の位置を x として、y=x+Aとする。x にある蓮を消して、y に移動する。
- y=N-1 ならば、ゲームが終了する。
- そうでなくて、y に蓮があるならば、得点が s_y 増加する。
- そこに蓮がないならば、あなたは溺れる。得点が 10^{100} 減少して、ゲームが終了する。
-
3.現在の位置を x として、y=x-Bとする。x にある蓮を消して、y に移動する。
- y=N-1 ならば、ゲームが終了する。
- そうでなくて、y に蓮があるならば、得点が s_y 増加する。
- そこに蓮がないならば、あなたは溺れる。得点が 10^{100} 減少して、ゲームが終了する。
-
4.手順2に戻る。
あなたは、最終得点をできるだけ大きくしたいです。 最適に A,B の値を決めたときの最終得点はいくらになるでしょうか。
制約
- 3 \leqq N \leqq 10^5
- -10^9 \leqq s_i \leqq 10^9
- s_0=s_{N-1}=0
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられます。
N
s_0 s_1 ...... s_{N-1}
出力
最適に A,B の値を決めたときの最終得点を出力してください。
入力例 1
5 0 2 5 1 0
出力例 1
3
A = 3, B = 2 としたとき、ゲームは次のように進行します。
- 座標 0 + 3 = 3 に移動し、得点が s_3 = 1 増加する。
- 座標 3 - 2 = 1 に移動し、得点が s_1 = 2 増加する。
- 座標 1 + 3 = 4 に移動し、得点 3 でゲームが終了する。
得点 4 以上でゲームを終了することはできないため、答えは 3 です。座標 2 にある蓮に乗ってその後溺れずに済ますことはできないことに注意してください。
入力例 2
6 0 10 -7 -4 -13 0
出力例 2
0
ここでの最適な戦略は、A = 5 を選んで (B の値は不問) ただちに最後の蓮に乗ることです。
入力例 3
11 0 -4 0 -99 31 14 -15 -39 43 18 0
出力例 3
59
Score : 600 points
Problem Statement
There is an infinitely large pond, which we consider as a number line. In this pond, there are N lotuses floating at coordinates 0, 1, 2, ..., N-2 and N-1. On the lotus at coordinate i, an integer s_i is written.
You are standing on the lotus at coordinate 0. You will play a game that proceeds as follows:
- 1. Choose positive integers A and B. Your score is initially 0.
- 2. Let x be your current coordinate, and y = x+A. The lotus at coordinate x disappears, and you move to coordinate y.
- If y = N-1, the game ends.
- If y \neq N-1 and there is a lotus floating at coordinate y, your score increases by s_y.
- If y \neq N-1 and there is no lotus floating at coordinate y, you drown. Your score decreases by 10^{100} points, and the game ends.
- 3. Let x be your current coordinate, and y = x-B. The lotus at coordinate x disappears, and you move to coordinate y.
- If y = N-1, the game ends.
- If y \neq N-1 and there is a lotus floating at coordinate y, your score increases by s_y.
- If y \neq N-1 and there is no lotus floating at coordinate y, you drown. Your score decreases by 10^{100} points, and the game ends.
- 4. Go back to step 2.
You want to end the game with as high a score as possible. What is the score obtained by the optimal choice of A and B?
Constraints
- 3 \leq N \leq 10^5
- -10^9 \leq s_i \leq 10^9
- s_0=s_{N-1}=0
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
s_0 s_1 ...... s_{N-1}
Output
Print the score obtained by the optimal choice of A and B.
Sample Input 1
5 0 2 5 1 0
Sample Output 1
3
If you choose A = 3 and B = 2, the game proceeds as follows:
- Move to coordinate 0 + 3 = 3. Your score increases by s_3 = 1.
- Move to coordinate 3 - 2 = 1. Your score increases by s_1 = 2.
- Move to coordinate 1 + 3 = 4. The game ends with a score of 3.
There is no way to end the game with a score of 4 or higher, so the answer is 3. Note that you cannot land the lotus at coordinate 2 without drowning later.
Sample Input 2
6 0 10 -7 -4 -13 0
Sample Output 2
0
The optimal strategy here is to land the final lotus immediately by choosing A = 5 (the value of B does not matter).
Sample Input 3
11 0 -4 0 -99 31 14 -15 -39 43 18 0
Sample Output 3
59