No.3656 Game Scores and Costs
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
くらげ
sepa38