問題一覧 > 通常問題

No.3646 Decrement.

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 9
作問者 : kazuppa / テスター : Tamiji153 Unbakedbread
ProblemId : 13867 / Paken新入生コンday2 (順位表) / 自分の提出
問題文最終更新日: 2026-08-25 18:39:02
Paken新入生コンday2の他の問題:

問題文

長さ $N$ の非負整数列 $(A_1,A_2,...,A_N)$ が与えられます。

あなたは $1\leq i\leq N$ を満たす整数 $i$ を一つ選び、$A_i$ を $1$ 減算するという操作を $K$ 回まで好きな回数（$0$ 回でも可）行うことができます。

適切に操作を行った時の $\displaystyle\sum_{i=0}^{N} |A_i-A_{i+1}|$ は最小でいくつになるか求めてください。ただし、$A_0=A_{N+1}=0$ であるものとします。

制約

  • $1\leq N\leq 2\times 10^5$
  • $0\leq K\leq 2\times 10^{14}$
  • $0\leq A_i\leq 10^9$
  • 入力はすべて整数

小課題

この問題にはサブタスクによる部分点が設定されています。

小課題名 配点 制約
小課題15 %$N=1$
小課題25 %$N=2$
小課題320 %$N\leq7,\ K\leq7$
小課題430 %$N\leq2000,\ K\leq2000$
小課題510 %$N\leq2000$
小課題630 %追加の制約はない

入力

$N\ K$
$A_1\ A_2\ \dotsc\ A_N$

出力

答えを一行に出力してください。

サンプル

サンプル1
入力
6 11
1 6 9 2 3 1
出力
6

$A_2$ を $4$ 回、$A_3$ を $7$ 回減算した $A=(1,2,2,2,3,1)$ は $\displaystyle\sum_{i=0}^{N} |A_i-A_{i+1}|=6$ となります。

答えを $6$ 未満にすることはできないので $6$ が答えです。

サンプル2
入力
5 100
0 0 0 0 0
出力
0

一回も操作をする必要がありません。

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