Skip to content
Sign in

ケーキの切り分け２ (Cake 2)

Unrated
日本語

Language

Contribute a translation
Time limit
2000 ms
Memory limit
512 MB
Submissions
0
Correct
0
Solved by
0
AC rate
—

Statement

JOI くんと IOI ちゃんは双子の兄妹である．JOI くんは最近お菓子作りに凝っていて，今日も JOI くんはケーキを焼いて食べようとしたのだが，焼きあがったところで匂いをかぎつけた IOI ちゃんが来たので \(2\) 人でケーキを分けることになった．

ケーキは円形である．ある点から放射状に切り目を入れ，ケーキを \(N\) 個のピースに切り分け，ピースに \(1\) から \(N\) まで反時計回りに番号をつけた．つまり，\(1 \leqq i \leqq N\) に対し，\(i\) 番目のピースは \(i - 1\) 番目と \(i + 1\) 番目のピースと隣接している (ただし \(0\) 番目は \(N\) 番目，\(N + 1\) 番目は \(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 ちゃんからはじめて IOI ちゃんと JOI くんが交互に残りのピースを \(1\) つずつ取っていく．ただし，両隣のピースのうち少なくとも一方が既に取られているようなピースしか取ることができず，取れるピースが複数あるときは，IOI ちゃんはそのうち最も大きいものを選んで取り，JOI くんはそのうちで好きなものを選んで取ることができる．

JOI くんは，自分が最終的に取るピースの大きさの合計を最大化したい．

課題

ケーキのピースの数 \(N\) と，\(N\) 個のピースの大きさの情報が与えられたとき，JOI くんが取れるピースの大きさの合計の最大値を求めるプログラムを作成せよ．

Input

標準入力から以下の入力を読み込め．

  • \(1\) 行目には整数 \(N\) が書かれており，ケーキが \(N\) 個のピースに切り分けられていることを表す．
  • 続く \(N\) 行のうちの \(i\) 行目 (\(1 \leqq i \leqq N\)) には整数 \(A_i\) が書かれており，\(i\) 番目のピースの大きさが \(A_i\) であることを表す．

Output

標準出力に，JOI くんが取れるピースの大きさの合計の最大値を表す整数を \(1\) 行で出力せよ．

Constraints

すべての入力データは以下の条件を満たす．

  • \(1 \leqq N \leqq 2\,000\)．
  • \(1 \leqq A_i \leqq 1\,000\,000\,000\)．
  • \(A_i\) はすべて異なる．

Subtasks

小課題 1 [15 点]

  • \(N \leqq 20\) を満たす．

小課題 2 [45 点]

  • \(N \leqq 300\) を満たす．

小課題 3 [40 点]

追加の制限はない．

Examples

Sample input 1
5
2
8
1
10
9
Sample output 1
18

JOI くんは，次のようにピースを取るのが最適である．

  1. JOI くんは \(2\) 番目のピースを取る．このピースの大きさは \(8\) である．
  2. IOI ちゃんは \(1\) 番目のピースを取る．このピースの大きさは \(2\) である．
  3. JOI くんは \(5\) 番目のピースを取る．このピースの大きさは \(9\) である．
  4. IOI ちゃんは \(4\) 番目のピースを取る．このピースの大きさは \(10\) である．
  5. JOI くんは \(3\) 番目のピースを取る．このピースの大きさは \(1\) である．

最終的に，JOI くんが取ったピースの大きさの合計は，\(8 + 9 + 1 = 18\) となる．

Sample input 2
8
1
10
4
5
6
2
9
3
Sample output 2
26
Sample input 3
15
182243672
10074562
977552215
122668426
685444213
3784162
463324752
560071245
134465220
21447865
654556327
183481051
20041805
405079805
564327789
Sample output 3
3600242976

Notes

JOI 2015 · JCIOI · CC BY-SA 4.0

Tags

No tags yet

Source