A - カードと兄妹
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
N 枚のカードがあり、i (1 ≦ i ≦ N) 枚目のカードには整数 A_i が書かれています。ゲーム好きの兄妹はこれらのカードを使ってゲームをしようとしています。
- 最初に全てのカードを、カードに書かれた整数が見えるようにテーブルの上に並べる。
- プレイヤーは自分のターンに、テーブルの上にあるカードからちょうど 1 枚のカードを選んで取る。
- テーブルの上にカードがなくなるまで、交互にターンを繰り返す。
- 最終的に、自分が取ったカードに書かれた整数の和がプレイヤーの スコア となる。
2 人ともが自分のスコアを出来るだけ大きくしようとしたとき、先手のスコアはいくつになるでしょうか?
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 ... A_N
- 1 行目には、カードの枚数を表す整数 N (1 ≦ N ≦ 1000) が与えられる。
- 2 行目には、各カードに書かれた整数を表す N 個の整数が空白区切りで与えられる。このうち i (1 ≦ i ≦ N) 番目の整数 A_i (1 ≦ A_i ≦ 1000) は、i 枚目のカードに書かれた整数を表す。
出力
先手のスコアを 1 行に出力せよ。出力の末尾に改行を入れること。
入力例1
2 400 628
出力例1
628
この例では、ゲームは以下のように進行します。
- 先手が 2 枚目のカードを取る。
- 後手が 1 枚目のカードを取る。
このとき、先手のスコアは 628 となり、後手のスコアは 400 となります。
入力例2
5 2 5 9 6 5
出力例2
16
この例では、ゲームは以下のように進行します。
- 先手が 3 枚目のカードを取る。
- 後手が 4 枚目のカードを取る。
- 先手が 2 枚目のカードを取る。
- 後手が 5 枚目のカードを取る。
- 先手が 1 枚目のカードを取る。
このとき、先手のスコアは 16 となり、後手のスコアは 11 となります。