F - 青蛙跳跃

分数：600分

问题描述

有一个无限大的池塘，我们将其视为一条数轴。 在这个池塘上有$N$朵睡莲，它们浮在坐标$0$，$1$，$2$，...，$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$能获得多少分？

约束

• $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$的最佳分数。

5
0 2 5 1 0

3

如果选择$A = 3$和$B = 2$，游戏的进行如下：

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

不存在以$4$或更高分数结束游戏的方法，因此答案是$3$。注意在淹死之前你无法降落到坐标$2$上的睡莲。

6
0 10 -7 -4 -13 0

0

这里的最佳策略是通过选择$A = 5$（$B$的值不重要）立即落在最后一个睡莲上。

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

59