問題一覧 > 通常問題

No.1374 Absolute Game

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 111
作問者 : leaf_1415leaf_1415 / テスター : tempura_pptempura_pp
13 ProblemId : 2803 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-01-25 14:29:19

問題文

A君とB君はカードゲームで対戦しています。
ゲームが始まる前には、テーブルの上には $N$ 枚のカードが置かれています。
それぞれのカードには整数が書かれており、$i$ 番目のカードに書かれている整数は $c_i$ です。

ゲームはA君が先手で開始され、2人で交互に手番を行っていきます。
手番になったプレイヤーは、テーブルの上から任意に1枚のカードを選んで獲得します。
テーブルの上からカードが無くなったとき、ゲームは終了です。
獲得したカードに書かれている整数の合計が、プレイヤーの「得点」になります。
両プレイヤーは、相手よりも出来るだけ多くの得点を得ることを目指します。

2人にとってこのゲームはあまりに簡単すぎたので、彼らはルールを少し変更することにしました。
獲得したカードの合計値を得点とする代わりに、新しいルールではカードの合計値の絶対値を得点とすることにしました。
つまり、ゲーム終了時にA君が獲得しているカードの合計値を $a$ とし、B君が獲得しているカードの合計値を $b$ とすると、
A君の得点は $|a|$ となり、B君の得点は $|b|$ となります。

ゲームの「得点差」を $|a| - |b|$ で定義します。ここで定義する「得点差」は負の値にもなりうることに注意してください。
A君は得点差を出来るだけ大きくすることを目指し、B君は得点差を出来るだけ小さくすることを目指します。
2人が最善の行動をとったときの得点差を出力してください。

入力

$N$
$c_1\ c_2\ \ldots\ c_N$

入力は以下の制約を満たします。
$1 \leq N \leq 10^5$
$0 \leq |c_i| \leq 10^9$
入力値はすべて整数

出力

2人が最善の行動をとったときの得点差を1行に出力してください。 最後に改行してください。

サンプル

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

まずA君が $4$ のカードを獲得し、次にB君が $-2$ のカードを獲得し、
最後にA君が $-1$ のカードを取るのが進行の一例です。
$a = 4 + (-1) = 3$ なのでA君の得点は $|a| = 3$ となり、
$b = -2$ なのでB君の得点は $|b|=2$ となります。
よって、得点差は $|a|-|b|=1$ となります。

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

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