← 返回题目列表

AtCoder · abc128_f

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.
    • 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