No.3303 Heal Slimes 2
dyktr_06
sepa38
くらげ
Nafmo2
問題文最終更新日: 2025-10-04 18:13:27
English (AI translation)
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 MMA Contest 020
(順位表)
の他の問題:
Problem Statement
You keep $N$ slimes.
The slimes are lined up in a row, and the HP of the $i$-th slime is $H_i$.
You can cast the following $2$ types of healing magic any number of times, in any order.
- Choose an integer $i$ satisfying $1 \leq i \leq N$, and change the HP of the $i$-th slime by $+1$.
- Choose an integer $i$ satisfying $1 \leq i \leq N$, and change the HP of the $i$-th slime by $-1$.
Your goal is to make the following condition hold for some $K$ consecutive slimes.
- The maximum HP minus the minimum HP is at most $D$.
Find the minimum number of healing magic casts required to achieve the goal.
Constraints
- $2 \leq K \leq N \leq 10^{5}$
- $0 \leq D \leq 10^{9}$
- $0 \leq H_i \leq 10^{9}$
- All inputs are integers.
Input
The input is given from Standard Input in the following format.
$N$ $K$ $D$ $H_1$ $H_2$ $\cdots$ $H_N$
Output
Output the answer to the problem on one line.
Sample
Sample 1
Input
5 4 1 1 5 3 9 7
Output
6
For example, casting healing magic as follows achieves the goal with $6$ casts.
- Change the HP of the $3$-rd slime by $+1$. Its HP becomes $4$.
- Change the HP of the $3$-rd slime by $+1$. Its HP becomes $5$.
- Change the HP of the $4$-th slime by $-1$. Its HP becomes $8$.
- Change the HP of the $5$-th slime by $-1$. Its HP becomes $6$.
- Change the HP of the $4$-th slime by $-1$. Its HP becomes $7$.
- Change the HP of the $4$-th slime by $-1$. Its HP becomes $6$.
The HP of the $2$-nd through $5$-th slimes are $(5, 5, 6, 6)$, which confirms that the goal has been achieved.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。