← 返回题目列表

AtCoder · joi2015ho_b

B. 切蛋糕2(蛋糕2)

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

配点: 100 点

JOI君和IOI酱是双胞胎兄妹。 JOI君最近开始热衷于烘焙,今天烤了一个蛋糕,正准备吃,结果烘焙完成后,IOI酱闻到了香味,走了过来。 2 决定把蛋糕分给大家。

蛋糕是圆形的。从某一点开始放射状切割并切蛋糕。 N 切成块; 逆时针编号至 1 到 N 。换句话说, 对于1 \leqq i \leqq N , 第i 块是 i - 1 th 和 它与 i + 1 块相邻(但是 0 th 是 N 番目,N + 1 th 是 1 )。i 块的大小是 A_i ,但我剪得非常不好,所以 A_i 都有不同的值。

図 1: ケーキの例 (<var>N = 5</var>,<var>A_1 = 2</var>,<var>A_2 = 8</var>,<var>A_3 = 1</var>,<var>A_4 = 10</var>,<var>A_5 = 9</var>)

这个 我决定将 N 碎片分给JOI君和IOI酱。我决定将其划分如下:

  1. 首先,JOI君。 N 最喜欢的作品 1 选择一项。
  2. 之后,IOI酱和JOI君轮流捡起剩下的棋子,从IOI酱开始。 1 一一拿走。不过,只能在双方至少有一个棋子已经被拿走的情况下拿走一颗棋子,如果有多个可以拿走的棋子,IOI-chan可以选择最大的一个并拿走它,而JOI-kun可以选择他喜欢的一个并拿走它。

JOI-kun 想要最大化他最终获得​​的棋子的总大小。

課題

蛋糕块数 N 和 编写一个程序,根据N 片段大小的信息,计算 JOI 可以占用的片段总大小的最大值。


入力

从标准输入读取以下输入。 写着

  • 1 行是一个整数 N ,蛋糕是 表示它被切成 N 块。
  • 继续 N 行 i 行目 (1 \leqq i \leqq N) 是一个整数 写入 A_i ,i 块的大小是 A_i 。

出力

表示 JOI-kun 可以拿走的最大棋子总尺寸的整数被发送到标准输出。 输出为 1 行。


制限

所有输入数据满足以下条件。

  • 1 \leqq N \leqq 2\,000.
  • 1 \leqq A_i \leqq 1\,000\,000\,000.
  • A_i 都是不同的。

小課題

小課題 1 [15 点]

  • N \leqq 20 满意。

小課題 2 [45 点]

  • N \leqq 300 满意。

小課題 3 [40 点]

没有其他限制。


入力例 1

5
2
8
1
10
9

出力例 1

18

JOI君最好按如下方式拿走棋子。

  1. JOI-kunha 拿走第 2 块。这件作品的尺寸是 8 。
  2. IOI酱 1 块。这件作品的尺寸是 2 。
  3. JOI-kunha 拿走第 5 块。这件作品的尺寸是 9 。
  4. IOI酱 4 块。这件作品的尺寸是 10 。
  5. JOI-kunha 拿走第 3 块。这件作品的尺寸是 1 。

最后,JOI君拿走的棋子的总大小是8 + 9 + 1 = 18 变为。


入力例 2

8
1
10
4
5
6
2
9
3

出力例 2

26

入力例 3

15
182243672
10074562
977552215
122668426
685444213
3784162
463324752
560071245
134465220
21447865
654556327
183481051
20041805
405079805
564327789

出力例 3

3600242976