Problem description

Back
Show PDF
Klocki
(B)
Limit pamięci: 256 MB
Limit czasu: 2.00 s

Bajtazar postanowił przygotować na wystawę artystyczną instalację złożoną z podświetlanych klocków.
Ustawił je w N stosów, ponumerowanych od 1 do N. Wysokość i-tego stosu oznaczymy przez Si.

Przykładowe ustawienie klocków dla N = 20

Komisja bezpieczeństwa festiwalu stwierdziła jednak, że instalacja może być niebezpieczna. Uznano, że dzieło jest bezpieczne tylko wtedy, gdy wysokości sąsiednich stosów nie różnią się o więcej niż H klocków, tzn. dla każdego 1 ≤ i < N zachodzi |Si − Si + 1| ≤ H.

Bajtazar nie chce usuwać swojej instalacji, ale może ją zmodyfikować. W jednej operacji może:

  • dodać jeden klocek na szczyt wybranego stosu,
  • usunąć jeden klocek z wierzchu wybranego stosu (o ile ten stos nie jest pusty).

Bajtazar chce wykonać jak najmniej operacji, aby jego instalacja stała się bezpieczna.
Twoim zadaniem jest obliczenie minimalnej liczby potrzebnych operacji.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite N oraz H – odpowiednio liczba stosów oraz maksymalna dozwolona różnica wysokości sąsiednich stosów.

W drugim (i ostatnim) wierszu wejścia znajduje się N nieujemnych liczb całkowitych oddzielonych pojedynczymi spacjami – wysokości S1, S2, …, SN kolejnych stosów.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna znaleźć się pojedyncza liczba całkowita – minimalna liczba operacji, które musi wykonać Bajtazar, aby jego instalacja stała się bezpieczna.

Ograniczenia

1 ≤ N ≤ 200 000, 0 ≤ H ≤ 109, 0 ≤ Si ≤ 109 dla każdego 1 ≤ i ≤ N

Podzadania

Podzadanie Warunki Punkty
1 N ≤ 10, Si ≤ 4 3
2 N ≤ 14, H ≤ 1, Si ≤ 4 4
3 N ≤ 10, H ≤ 2 9
4 H = 0 5
5 N ≤ 500, Si ≤ 400 6
6 N ≤ 500, Si ≤ 5000 11
7 N ≤ 5 000, Si ≤ 5 000 11
8 N ≤ 5 000 22
9 brak dodatkowych ograniczeń 29

Przykład

Wejście Wyjście Wyjaśnienie 
6 1
2 10 0 2 4 3

10

Bajtazar może zabrać 7 klocków z drugiego stosu, następnie dodać 2 klocki na trzeci stos, oraz 1 klocek na czwarty stos.
Wejście Wyjście 
6 3
2 10 2 6 4 3

6
Wejście Wyjście 
4 1
1 4 1 4

4
Wejście Wyjście 
10 1
10 9 8 7 6 5 4 3 2 1

0
Wejście Wyjście 
3 0
1 1 3

2