問題一覧 > 通常問題

No.1687 What the Heck?

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 168
作問者 : ansainansain / テスター : noya2noya2 ygussanyygussany
12 ProblemId : 6500 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-09-24 21:50:44

問題文

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

  • $2$ 人のプレイヤーは最初 $1$ から $N$ の整数が書かれたカードをそれぞれ $1$ 枚ずつ、合計 $N$ 枚持っている。
  • ゲームは $N$ ラウンドからなる。$i$ $(1 \le i \le 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 \le N \le 2\times 10^5$
  • $P$ は $1$ から $N$ までの整数を並び替えた順列
  • 入力はすべて整数

    • 出力

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

    サンプル

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

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

    サンプル2
    入力
    1
1
    出力
    0

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

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