ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
Placeholder

#8477
サブタスク

소들의 키 3s 1024MB

問題

농부 John 은 N 마리의 소들을 키우고 있다.

i 번째 소의 키는 H_i 이다. (~i~= ~1,~ 2,~ ...~ , ~ N ~)

John 의 목표는 모든 인접한 소의 키 차이가 K 이하가 되게 만드는 것이다.

즉, 모든 1 ≤ i < N 에 대해 |H_{i+1}-H_i|≤K 가 되는 것이다.

John 은 1원의 비용을 들여, 소 하나를 골라 키를 원하는 정수로 바꿀 수 있다.

목표를 달성하기 위한 최소 비용을 구하자.


入力

첫 줄에 두 정수 N 과 K 가 입력된다. ( 1 ≤ N ≤ 50만, 0 ≤K≤ 1012 )

두 번째 줄에 각 소들의 키 H_i 가 입력된다. ( 각각 1012 이하의 자연수 )


出力

목표를 달성하기 위한 최소 비용을 출력한다.


部分問題

番号 点数 条件
#110点

K=0

#220点

1 ≤ N ≤ 20

#350点

1 ≤ N ≤ 1,000

#420点

제약 조건 없음


例題 #1

5 3
1 4 7 7 10000
1

마지막 소의 키만 4~10 범위의 수로 바꾸면 된다.


例題 #2

12 2
1 8 3 5 19 23 38 21 18 4 5 1
7


出典

KCPC 2024 예비소집 C번

ログインしないとコードを書けません。