分数: 600 点
问题陈述
有一个无限大的池塘,我们将其视为一条数轴。 这个池塘里有 N 荷花漂浮在坐标处 0, 1, 2, ..., N-2 和 N-1。 位于莲花座标处 i,一个整数 写入 s_i 。
你正站在莲花上的坐标 0。您将玩一个按如下方式进行的游戏:
- 1。选择正整数 A 和 B。你的分数最初是 0.
- 2。让 x 是您当前的坐标,并且 y = x+A。坐标处的莲花 x 消失,你移动到坐标 y.
- If y = N-1,游戏结束。
- If y \neq N-1 坐标处有一朵莲花漂浮 y,您的分数增加 s_y.
- If y \neq N-1 并且坐标处没有漂浮的莲花 y,你淹死了。您的分数减少了 10^{100} 分,游戏结束。
- 3。让 x 是您当前的坐标,并且 y = x-B。坐标处的莲花 x 消失,你移动到坐标 y.
- If y = N-1,游戏结束。
- If y \neq N-1 坐标处有一朵莲花漂浮 y,您的分数增加 s_y.
- If y \neq N-1 并且坐标处没有漂浮的莲花 y,你淹死了。您的分数减少了 10^{100} 分,游戏结束。
- 4。返回步骤 2.
你想以尽可能高的分数结束游戏。 最优选择得到的分数是多少 A 和 B?
约束
- 3 \leq N \leq 10^5
- -10^9 \leq s_i \leq 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