소들의 키 3s 1024MB

Problems

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

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

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

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

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

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

Input

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

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

Output

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

Subtask

#	Score	Condition
#1	10	K=0
#2	20	1 ≤ N ≤ 20
#3	50	1 ≤ N ≤ 1,000
#4	20	제약 조건 없음

Example #1

5space_bar 3keyboard_return
1space_bar 4space_bar 7space_bar 7space_bar 10000

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

Example #2

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

Tag

Source

KCPC 2024 예비소집 C번

You must sign in to write code.

#8477 upload 266 done 37 how_to_reg 31 call_split Subtask

소들의 키 timer 3s memory 1024MB

Problems text_fields