No.1687 What the Heck?

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.1687 What the Heck?

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 170
作問者 :

ansain / テスター :

noya2 👑

ygussany

13 ProblemId : 6500 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2021-09-24 21:50:44

問題文

武田さんと鈴木さんは次のようなルールのゲームで遊んでいます。

2

人のプレイヤーは最初

1

から

N

の整数が書かれたカードをそれぞれ

1

枚ずつ、合計

N

枚持っている。

ゲームは

N

ラウンドからなる。

i

(1 \leq i \leq N)

回目のラウンドでは、プレイヤーは一斉に持っているカードの中からカードを

1

枚出す。その後、出されたカードの整数を比較する。

2

人の出した整数が異なる場合、大きい整数を出した方が

i

点を得る。

同じ人が同じ整数のカードを複数のラウンドで出すことはできない。

武田さんは予知能力者なので、鈴木さんがどのラウンドにどのカードを出すかを知っています。鈴木さんが出すカードは $1$ から $N$ までの整数を並び替えた順列 $(P_{1}, P_{2}, \dots, P_{N})$ で表され、 $i$ 回目のラウンドで出すカードは $P_{i}$ です。武田さんがカードを出す順番を選ぶことで実現できる (武田さんがゲーム中に得る得点の合計) $-$ (鈴木さんがゲーム中に得る得点の合計) の最大値はいくつですか？

入力

 $N$ 
 $P_{1}$   $P_{2}$   $\dots$   $P_{N}$

1 \leq N \leq 2 \times 10^{5}

P

は

1

から

N

までの整数を並び替えた順列

入力はすべて整数

出力

(武田さんがゲーム中に得る得点の合計) $-$ (鈴木さんがゲーム中に得る得点の合計)の最大値を出力してください。最後に改行してください。

サンプル

サンプル1

入力

3
3 1 2

出力

武田さんはラウンド $1$ に $1$ ,ラウンド $2$ に $2$ ,ラウンド $3$ に $3$ を出すことで、武田さんはラウンド $2, 3$ で得点を獲得し、鈴木さんはラウンド $1$ で得点を獲得します。得点差は $4$ 点になりこれが最大です。

サンプル2

入力

1
1

出力

武田さんも $1$ ラウンド目に $1$ を出すしかありません。 $1$ ラウンド目に $1$ という同じ整数のカードを武田さんと鈴木さんが出しているので、双方得る得点は $0$ 点です。

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

yukicoder

No.1687 What the Heck?

問題文

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力