← 返回题目列表

AtCoder · abc285_e

H. 工作还是休息

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

在高桥生活的世界里,一周有 N 天。

AtCoder 王国的国王高桥为一周中的每一天指定“工作日”或“假日”。 所有几周的作业都应该是相同的。 一周中至少一天应指定为“假期”。

在这样的条件下,生产效率 i- 一周中的第一天由序列定义 A 长度 N 如下:

  • 如果 i- 一周中的第几天是“假期”,其生产率为 0;
  • 如果 i- 一周中的第一天是“工作日”,它的生产率是 A_{\min(x,y)},如果最后一个假期是 x 前天和后天是 y 天后。
    • 请注意,由于定期分配,上一个/下一个假期可能属于不同的周。 详细信息请参见示例。

找出最佳选择作业时每周的最大生产力。
这里,每周的生产率是指每周的生产率的总和。 1-st, 2-nd, \dots,和 N- 一周中的第一天。

约束

  • 输入中的所有值都是整数。
  • 1 \le N \le 5000
  • 1 \le A_i \le 10^9

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \dots A_N

输出

将答案打印为整数。


示例输入 1

7
10 10 1 1 1 1 1

示例输出 1

50

例如,我们可以将“假期”分配给 2-nd 和 4- 一周中的第一天和其余的“工作日”,以实现生产力 50 每周:

  • 这 1- 一周中的第一天... x=4 和 y=1,所以它的生产率是 A_1 = 10.
  • 这 2- 一周中的第几天......这是假期,所以它的生产力是 0.
  • 这 3- 一周中的第一天... x=1 和 y=1,所以它的生产率是 A_1 = 10.
  • 这 4- 一周中的第几天......这是假期,所以它的生产力是 0.
  • 这 5一周中的第几天... x=1 和 y=4,所以它的生产率是 A_1 = 10.
  • 这 6一周中的第几天... x=2 和 y=3,所以它的生产率是 A_2 = 10.
  • 这 7一周中的第几天... x=3 和 y=2,所以它的生产率是 A_2 = 10.

每周的生产力是不可能的 51 或更大。


示例输入 2

10
200000000 500000000 1000000000 800000000 100000000 80000000 600000 900000000 1 20

示例输出 2

5100000000

示例输入 3

20
38 7719 21238 2437 8855 11797 8365 32285 10450 30612 5853 28100 1142 281 20537 15921 8945 26285 2997 14680

示例输出 3

236980