問題一覧 > 通常問題

No.999 てん vs. ほむ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 263
作問者 : tempura_pptempura_pp / テスター : tsutajtsutaj
16 ProblemId : 3977 / 出題時の順位表
問題文最終更新日: 2020-02-27 22:17:44

問題文

$2N$ 枚のカードが横一列に並んでいて、左から $i$ 枚目のカードには整数 $A_i$ が書かれています。
ほむらちゃんはてんぷらくんと次のようなゲームをして遊ぼうと思っていました。

  1. ほむらちゃんがその時点で列に残っているカードのうち、左端または右端のカードを $1$ 枚選び、 書かれている数を点数として獲得する。選んだカードは破棄する。
  2. てんぷらくんがその時点で列に残っているカードのうち、左端または右端のカードを $1$ 枚選び、 書かれている数を点数として獲得する。選んだカードは破棄する。
  3. $1, 2$ を $N$ 回繰り返す。
  4. $N$ 回で獲得した点数の合計の大きいほうが勝ち。
ところが、てんぷらくんはほむらちゃんのことが大好きなので、ほむらちゃんが左端のカードを選んだ直後には 自分も左端のカードを、ほむらちゃんが右端のカードを選んだ直後には自分も右端のカードを選んでしまいます。
このとき、$N$ 回の手順が終了したあとの、(ほむらちゃんの獲得した点数の合計)$-$(てんぷらくんの獲得した点数の合計) として考えられる最大値を計算してください。

入力

$N$
$A_1\ A_2\ \cdots \ A_{2N}$

  • 入力はすべて整数
  • $1 \leq N \leq 100000$
  • $1 \leq A_i \leq 10^9$

出力

(ほむらちゃんの獲得した点数の合計)$-$(てんぷらくんの獲得した点数の合計) として考えられる最大値を出力してください。 最後に改行してください。

サンプル

サンプル1
入力
2
3 1 2 4
出力
4

例えばゲームは以下のように進行します。

  1. ほむらちゃんが左端の $3$ を選ぶ。
  2. てんぷらくんもほむらちゃんと同じく左端の $1$ を選ぶ。
  3. ほむらちゃんが右端の $4$ を選ぶ。
  4. てんぷらくんもほむらちゃんと同じく右端の $2$ を選ぶ。
このとき (ほむらちゃんの獲得した点数の合計)$-$(てんぷらくんの獲得した点数の合計) $=7-3=4$ 点で、これが最大値です。

サンプル2
入力
1
5 5
出力
0

サンプル3
入力
5
3 1 4 1 5 9 2 6 5 3
出力
11

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。