No.3646 Decrement.
タグ : / 解いたユーザー数 16
作問者 :
kazuppa
/ テスター :
Problem Statement
You are given a sequence of non-negative integers $(A_1,A_2,...,A_N)$ of length $N$.
You may perform the following operation any number of times up to $K$ (possibly $0$ times): choose one integer $i$ satisfying $1\leq i\leq N$ and subtract $1$ from $A_i$.
Find the minimum possible value of $\displaystyle\sum_{i=0}^{N} |A_i-A_{i+1}|$ when the operations are performed appropriately. Here, assume that $A_0=A_{N+1}=0$.
Constraints
- $1\leq N\leq 2\times 10^5$
- $0\leq K\leq 2\times 10^{14}$
- $0\leq A_i\leq 10^9$
- All input values are integers
Subtasks
This problem has partial scoring through subtasks.
| Subtask | Points | Constraints |
|---|---|---|
| Subtask 1 | 5 % | $N=1$ |
| Subtask 2 | 5 % | $N=2$ |
| Subtask 3 | 20 % | $N\leq7,\ K\leq7$ |
| Subtask 4 | 30 % | $N\leq2000,\ K\leq2000$ |
| Subtask 5 | 10 % | $N\leq2000$ |
| Subtask 6 | 30 % | No additional constraints |
Input
$N\ K$ $A_1\ A_2\ \dotsc\ A_N$
Output
Print the answer on a single line.
Sample
Sample 1
Input
6 11 1 6 9 2 3 1
Output
6
Subtracting from $A_2$ $4$ times and from $A_3$ $7$ times gives $A=(1,2,2,2,3,1)$, for which $\displaystyle\sum_{i=0}^{N} |A_i-A_{i+1}|=6$.
The answer cannot be made less than $6$, so the answer is $6$.
Sample 2
Input
5 100 0 0 0 0 0
Output
0
No operations need to be performed.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。