AT_abc128_f [ABC128F] Frog Jump

题目描述

有一个无限延伸的池塘，可以看作是一条数轴。在这个池塘上漂浮着 $N$ 朵莲花，分别位于坐标 $0, 1, 2, \ldots, N-2, N-1$。

你一开始站在坐标 $0$ 的莲花上。你决定按照以下步骤进行游戏：

1. 选择正整数 $A, B$。初始得分为 $0$。

2. 设当前位置为 $x$，则令 $y = x + A$。消除 $x$ 处的莲花，并移动到 $y$。

   • 如果 $y = N-1$，则游戏结束。
   • 否则，如果 $y$ 处有莲花，则得分增加 $s_y$。
   • 如果 $y$ 处没有莲花，则你会溺水，得分减少 $10^{100}$，游戏结束。

3. 设当前位置为 $x$，则令 $y = x - B$。消除 $x$ 处的莲花，并移动到 $y$。

   • 如果 $y = N-1$，则游戏结束。
   • 否则，如果 $y$ 处有莲花，则得分增加 $s_y$。
   • 如果 $y$ 处没有莲花，则你会溺水，得分减少 $10^{100}$，游戏结束。

4. 返回步骤 2。

你希望最终得分尽可能大。请问最优选择 $A, B$ 时，最终得分最大是多少？

输入格式

输入通过标准输入给出，格式如下：

$N$ $s_0$ $s_1$ $\ldots$ $s_{N-1}$

输出格式

请输出最优选择 $A, B$ 时的最大最终得分。

样例 1

输入

5
0 2 5 1 0

输出

3

样例 2

输入

6
0 10 -7 -4 -13 0

输出

0

样例 3

输入

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$
• 所有输入均为整数。

样例解释 1

当 $A=3, B=2$ 时，游戏过程如下：

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

无法通过其他方式获得得分 $4$ 或更高，因此答案为 $3$。注意，不能在坐标 $2$ 的莲花上停留而不溺水。

样例解释 2

此时最优策略是选择 $A=5$（$B$ 的值无所谓），直接跳到最后一朵莲花即可。

由 ChatGPT 4.1 翻译