問題一覧 > 通常問題

No.999 Ten vs. Homu

レベル : / AI推定難易度 : 775 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 344
作問者 : tempura_pp / テスター : tsutaj
お気に入りにしたユーザー ProblemId : 3977 / 自分の提出
問題文最終更新日: 2020-02-27 22:17:44
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 239 (順位表) の他の問題:

Problem Statement

$2N$ cards are arranged in a horizontal row, and the $i$-th card from the left has the integer $A_i$ written on it.
Homura-chan was going to play the following game with Tempura-kun.

  1. Homura-chan chooses $1$ card, either the leftmost or the rightmost among the cards remaining in the row at that point, and gains the number written on it as points. The chosen card is discarded.
  2. Tempura-kun chooses $1$ card, either the leftmost or the rightmost among the cards remaining in the row at that point, and gains the number written on it as points. The chosen card is discarded.
  3. Repeat $1, 2$ a total of $N$ times.
  4. The player with the larger total of points gained over the $N$ rounds wins.
However, because Tempura-kun loves Homura-chan so much, right after Homura-chan chooses the leftmost card he also chooses the leftmost card, and right after Homura-chan chooses the rightmost card he also chooses the rightmost card.
Under these conditions, calculate the maximum possible value of (Homura-chan's total points)$-$(Tempura-kun's total points) after the $N$ rounds have finished.

Input

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

  • All inputs are integers.
  • $1 \leq N \leq 100000$
  • $1 \leq A_i \leq 10^9$

Output

Output the maximum possible value of (Homura-chan's total points)$-$(Tempura-kun's total points). Print a newline at the end.

Sample

Sample 1
Input
2
3 1 2 4
Output
4

For example, the game proceeds as follows.

  1. Homura-chan chooses the leftmost card, $3$.
  2. Tempura-kun, like Homura-chan, chooses the leftmost card, $1$.
  3. Homura-chan chooses the rightmost card, $4$.
  4. Tempura-kun, like Homura-chan, chooses the rightmost card, $2$.
In this case, (Homura-chan's total points)$-$(Tempura-kun's total points) $=7-3=4$ points, and this is the maximum value.

Sample 2
Input
1
5 5
Output
0

Sample 3
Input
5
3 1 4 1 5 9 2 6 5 3
Output
11

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