Frog Jump

题目描述

有一个无限大的池塘，我们把它看作数轴。 在这个池塘上，有 $N$ 个荷叶分别漂浮在坐标 $0, 1, 2, \dots, N-2, N-1$ 上。 在坐标为 $i$ 的荷叶上，写着一个整数 $s_i$。 你站在坐标 $0$ 的荷叶上。你将进行以下游戏：

$1$. 选择正整数 $A$ 和 $B$。你的初始得分为 $0$。 $2$. 设 $x$ 为你当前的坐标，$y = x+A$。坐标 $x$ 的荷叶消失，你移动到坐标 $y$。 如果 $y = N-1$，游戏结束。 如果 $y \neq N-1$ 且在坐标 $y$ 处有荷叶漂浮，则你的得分增加 $s_y$。 如果 $y \neq N-1$ 且在坐标 $y$ 处没有荷叶漂浮，你会溺水。你的得分减少 $10^{100}$ 分，游戏结束。

$3$. 设 $x$ 为你当前的坐标，$y = x-B$。坐标 $x$ 的荷叶消失，你移动到坐标 $y$。 如果 $y = N-1$，游戏结束。 如果 $y \neq N-1$ 且在坐标 $y$ 处有荷叶漂浮，则你的得分增加 $s_y$。 如果 $y \neq N-1$ 且在坐标 $y$ 处没有荷叶漂浮，你会溺水。你的得分减少 $10^{100}$ 分，游戏结束。

$4$. 返回到步骤 $2$。

你希望以尽可能高的得分结束游戏。 对于最优的 $A$ 和 $B$，可以得到多少得分？

输入格式

从标准输入读取输入，格式如下： $N$ $s_0$ $s_1$ $......$ $s_{N-1}$

输出格式

输出对于最优的 $A$ 和 $B$ 所能得到的得分。

5
0 2 5 1 0

3

6
0 10 -7 -4 -13 0

0

11
0 -4 0 -99 31 14 -15 -39 43 18 0

59

提示

$3 \leq N \leq 10^5$ $-10^9 \leq s_i \leq 10^9$ $s_0=s_{N-1}=0$ 输入中的所有值均为整数。如果你选择 $A = 3$ 和 $B = 2$，游戏过程如下：

移动到坐标 $0 + 3 = 3$。你的得分增加 $s_3 = 1$。 移动到坐标 $3 - 2 = 1$。你的得分增加 $s_1 = 2$。 移动到坐标 $1 + 3 = 4$。游戏以得分 $3$ 结束。

没有办法以得分 $4$ 或更高结束游戏，所以答案是 $3$。注意你不能在不随后溺水的情况下到达坐标 $2$。
这里的最优策略是通过选择 $A = 5$（$B$ 的值无关紧要）直接着陆到终点荷叶。

标签: AtCoder|abc128F

来源

AtCoder|abc128F