問題一覧 > 通常問題

No.3656 Game Scores and Costs

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 75
作問者 : くらげ / テスター : sepa38 dyktr_06 t5ugu yuusaan
お気に入りにしたユーザー ProblemId : 13922 / MMA Contest 022 (順位表) / 自分の提出
問題文最終更新日: 2026-08-29 16:14:36
MMA Contest 022の他の問題:

問題文

あるゲームを行うには $1$ 回ごとにコストを $X$ だけ払う必要があり、$1$ 回行うごとに得点が得られます。 くらげさんはこのゲームを $N$ 回行い、$i$ 回目のゲームでは $A_i$ 点を得ました。

$1$ 回目から $i$ 回目のゲームのうち得た得点が高い方から $\min(K,i)$ 回を選び、それらの得点の総和から $i$ 回のゲームにかかったコストを引いた値を $f(i)$ とします。

$i = 1, 2, \dots N$ について $f(i)$ を計算し、その最大値を求めてください。

制約

  • $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)$
  • 入力はすべて整数

入力

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

出力

答えを $1$ 行で出力してください。

サンプル

サンプル1
入力
5 2 20
30 20 70 10 60
出力
40

各 $i$ $(1 \le i \le 5)$ について $f(i)$ を計算すると以下のようになります。
$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$
以上より、$f(3) = 40$ が最大値です。

サンプル2
入力
3 2 100
10 10 10
出力
-90

$f(1) = 10 - 100 \times 1 = -90$ が最大です。

サンプル3
入力
10 10 0
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
出力
10000000000

答えが $32$ bit 整数型に収まらない場合があることに注意してください。

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