問題一覧 > 通常問題

No.3646 Decrement.

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 16
作問者 : kazuppa / テスター : Tamiji153 Unbakedbread
お気に入りにしたユーザー ProblemId : 13867 / 自分の提出
問題文最終更新日: 2026-08-25 18:39:02
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
Paken新入生コンday2 (順位表) の他の問題:

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 15 %$N=1$
Subtask 25 %$N=2$
Subtask 320 %$N\leq7,\ K\leq7$
Subtask 430 %$N\leq2000,\ K\leq2000$
Subtask 510 %$N\leq2000$
Subtask 630 %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もしくは右上の雲マークをクリックしてアカウントを作成してください。