問題一覧 > 通常問題

No.3656 Game Scores and Costs

レベル : / AI推定難易度 : 750 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 90
作問者 : くらげ / テスター : sepa38 dyktr_06 t5ugu yuusaan
お気に入りにしたユーザー ProblemId : 13922 / 自分の提出
問題文最終更新日: 2026-08-29 16:14:36
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
MMA Contest 022 (順位表) の他の問題:

Problem Statement

Playing a certain game requires paying a cost of $X$ per $1$ play, and a score is obtained for each $1$ play. Kurage played this game $N$ times and earned $A_i$ points in the $i$-th game.

Among the games from the $1$-st through the $i$-th, choose the $\min(K,i)$ games with the highest scores, and let $f(i)$ be the sum of their scores minus the cost spent on the $i$ games.

Compute $f(i)$ for $i = 1, 2, \dots N$ and find its maximum value.

Constraints

  • $1 \le K \le N \le 2 \times 10^5$
  • $0 \le X \le 10^9$
  • $0 \le A_i \le 10^9$ $(1 \le i \le N)$
  • All input values are integers.

Input

$N$ $K$ $X$
$A_1$ $A_2$ $\dots$ $A_N$

Output

Output the answer in $1$ line.

Sample

Sample 1
Input
5 2 20
30 20 70 10 60
Output
40

For each $i$ $(1 \le i \le 5)$, $f(i)$ is calculated as follows.
$f(1) = 30 - 20 \times 1 = 10$
$f(2) = 30+20 - 20 \times 2 = 10$
$f(3) = 30+70 - 20 \times 3 = 40$
$f(4) = 30+70 - 20 \times 4 = 20$
$f(5) = 70+60 - 20 \times 5 = 30$
Therefore, $f(3) = 40$ is the maximum value.

Sample 2
Input
3 2 100
10 10 10
Output
-90

$f(1) = 10 - 100 \times 1 = -90$ is the maximum.

Sample 3
Input
10 10 0
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Output
10000000000

Note that the answer may not fit in a $32$ bit integer type.

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