E - Greedy Ant

コンテスト時間: 2021-01-16 21:00:00+0900 ~ 2021-01-16 23:00:00+0900 (120分) AtCoderホームへ戻る

E - Greedy Ant 解説

実行時間制限: 3 sec / メモリ制限: 1024 MB

配点 : 700 点

問題文

数直線上に N 個の飴があります。左から i 番目の飴は位置 2i にあり、美味しさ a_i の飴です。ここで、飴の美味しさは相異なることが保証されます。

すぬけ君と蟻が交互に飴を一つずつ取り合うことにしました。はじめに蟻が位置 1,3,\ldots, 2N+1 の一つを選んでそこに立ち、取り合いを開始します。

すぬけ君が先に飴を取ります。すぬけ君は、自分の手番において好きな飴を一つ選んで取ることができます。

蟻は、自分の手番において、自分がいる位置から左右それぞれの方向について最も近い位置にある飴のうち、美味しさが大きい方を選んで取ります。一方向にしか飴が存在しない場合は、その方向にある最も近い位置にある飴を取ります。

飴がなくなった時点で取り合いは終了します。蟻がはじめに立つ位置が 1, 3, \ldots, 2N+1 の場合のそれぞれについて、すぬけ君が取る飴の美味しさの総和としてありうる値の最大値を求めてください。

制約

与えられる入力は全て整数
1 \leq N \leq 400
1 \leq a_i \leq 10^{6}
a_i は相異なる

入力

入力は以下の形式で標準入力から与えられる。

N
a_1 a_2 \ldots a_N

出力

N+1 行出力せよ。i 行目では、蟻がはじめに位置 2i-1 に立ったときに、すぬけ君が取る飴の美味しさの総和としてありうる値の最大値を出力すること。

入力例 1

7
4 3 1 2 1000 2000 3000

出力例 1

蟻がはじめに位置 7 に立ったときのすぬけ君の最適な戦略の一例について説明します。
- すぬけ君は美味しさ 1 の飴を取ります。
- 蟻の左方向にある蟻に最も近い飴は美味しさ 3 の飴です。蟻の右方向にある蟻に最も近い飴は美味しさ 2 の飴です。蟻は美味しさが大きい方である美味しさ 3 の飴を取ります。
- すぬけ君は美味しさ 1000 の飴を取ります。
- 蟻の左方向にある蟻に最も近い飴は美味しさ 4 の飴です。蟻の右方向にある蟻に最も近い飴は美味しさ 2 の飴です。蟻は美味しさが大きい方である美味しさ 4 の飴を取ります。
- すぬけ君は美味しさ 2000 の飴を取ります。
- 蟻の左方向にある蟻に最も近い飴は存在しません。蟻の右方向にある蟻に最も近い飴は美味しさ 2 の飴です。蟻は美味しさ 2 の飴を取ります。
- すぬけ君は美味しさ 3000 の飴を取ります。
- すぬけ君の取った飴の美味しさの総和は 6001 です。これを超えるようなすぬけ君の飴の取り方は存在しません。

入力例 2

40
45651 92206 55173 24815 34809 73343 60978 57984 6919 89624 19693 30037 87070 6713 65976 37597 51929 93304 70911 7343 65414 38977 47998 52123 53590 35714 59319 50872 53850 40991 85668 8808 32846 70831 3416 42173 89538 73410 21502 69631

出力例 2

Score : 700 points

Problem Statement

There are N candies on a number line. The i-th candy from the left is at the position 2i and has the tastiness of a_i. Here, it is guaranteed that the tastinesses of all candies are distinct.

Snuke and Ant have decided to play a game of alternately taking one candy. At the beginning of the game, Ant chooses one of the positions 1,3,\ldots, 2N+1 and stands there.

Snuke goes first. In his turn, he can choose any one candy and get it.

In Ant's turn, she chooses the candy with the greater tastiness of the following two: the nearest candy to the left of her and the nearest candy to the right of her. If there are candies in only one direction, she chooses the nearest one.

The game ends when no candies are left. For each of the positions 1, 3, \ldots, 2N+1, find the maximum possible sum of the tastinesses of candies Snuke takes when Ant chooses that position.

Constraints

All values in input are integers.
1 \leq N \leq 400
1 \leq a_i \leq 10^{6}
a_i are distinct.

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 \ldots a_N

Output

Print N+1 lines. The i-th line should contain the maximum possible sum of the tastinesses of candies Snuke takes when Ant initially stands at the position 2i-1.

Sample Input 1

7
4 3 1 2 1000 2000 3000

Sample Output 1

We will explain one optimal strategy for Snuke when Ant initially stands at the position 7.
- Snuke chooses the candy of tastiness 1.
- The candies to the left and right of Ant have the tastinesses of 3 and 2, respectively. She chooses the one with the greater tastiness, that is, the one with tastiness 3.
- Snuke chooses the candy of tastiness 1000.
- The candies to the left and right of Ant have the tastinesses of 4 and 2, respectively. She chooses the one with the greater tastiness, that is, the one with tastiness 4.
- Snuke chooses the candy of tastiness 2000.
- There is no candy to the left of Ant, and the candy to the right of Ant has the tastiness of 2. She chooses this candy with tastiness 2.
- Snuke chooses the candy of tastiness 3000.
- The sum of the tastinesses of candies Snuke has taken is 6001. There is no way to take candies that results in a greater total tastiness.

Sample Input 2

40
45651 92206 55173 24815 34809 73343 60978 57984 6919 89624 19693 30037 87070 6713 65976 37597 51929 93304 70911 7343 65414 38977 47998 52123 53590 35714 59319 50872 53850 40991 85668 8808 32846 70831 3416 42173 89538 73410 21502 69631

Sample Output 2