問題一覧 > 通常問題

No.1687 What the Heck?

レベル : / AI推定難易度 : 1300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 175
作問者 : ansain / テスター : noya2 ygussany
お気に入りにしたユーザー ProblemId : 6500 / 自分の提出
問題文最終更新日: 2021-09-24 21:50:44
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 315 (順位表) の他の問題:

Problem Statement

Takeda and Suzuki are playing a game with the following rules.

  • Initially, each of the $2$ players holds $1$ card for each integer from $1$ to $N$, for a total of $N$ cards.
  • The game consists of $N$ rounds. In round $i$ $(1 \le i \le N)$, the players simultaneously play $1$ card each from the cards they hold. Then, the integers on the played cards are compared. If the integers played by the $2$ players are different, the player who played the larger integer gets $i$ points.
  • The same player cannot play the card with the same integer in multiple rounds.

    • Takeda has precognition, so he knows which card Suzuki will play in each round. The cards Suzuki plays are represented by a permutation $(P_1, P_2, \dots, P_N)$ of the integers from $1$ to $N$, and the card he plays in round $i$ is $P_i$. What is the maximum value of (the total points Takeda gets during the game)$-$(the total points Suzuki gets during the game) that can be achieved by Takeda choosing the order in which he plays his cards?

    Input

    $N$
$P_1$ $P_2$ $\dots$ $P_N$
  • $1 \le N \le 2\times 10^5$
  • $P$ is a permutation of the integers from $1$ to $N$
  • All input values are integers

    • Output

    Print the maximum value of (the total points Takeda gets during the game)$-$(the total points Suzuki gets during the game). Print a newline at the end.

    Sample

    Sample 1
    Input
    3
3 1 2
    Output
    4

    If Takeda plays $1$ in round $1$, $2$ in round $2$, and $3$ in round $3$, Takeda scores points in rounds $2,3$, and Suzuki scores points in round $1$. The score difference is $4$ points, and this is the maximum.

    Sample 2
    Input
    1
1
    Output
    0

    Takeda also has no choice but to play $1$ in round $1$. Since Takeda and Suzuki both play a card with the same integer, $1$, in round $1$, both of them get $0$ points.

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