No.999 Ten vs. Homu
レベル :
/ AI推定難易度 : 775
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 344
作問者 :
tempura_pp
/ テスター :
tsutaj
タグ : / 解いたユーザー数 344
作問者 :
tempura_pp
/ テスター :
tsutaj
問題文最終更新日: 2020-02-27 22:17:44
English (AI translation)
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.
- 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.
- 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.
- Repeat $1, 2$ a total of $N$ times.
- The player with the larger total of points gained over the $N$ rounds wins.
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.
- Homura-chan chooses the leftmost card, $3$.
- Tempura-kun, like Homura-chan, chooses the leftmost card, $1$.
- Homura-chan chooses the rightmost card, $4$.
- Tempura-kun, like Homura-chan, chooses the rightmost card, $2$.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。