分数: 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