== include(page="template/taskheader" task_id="ktown") ==
Poveste şi cerinţă...
În oraşul Tecuci există $N$ clădiri situate în linie, fiecare având o anumită înălţime. Datorită riscului ridicat de furtuni cu fulgere în acea zonă, primarul oraşului a stabilit că înălţimile celor $N$ clădiri trebuie modificate astfel încât o clădire să fie mai înaltă cu cel puţin $K$ unităţi decât cea din stânga sa (dacă există o astfel de clădire).
Definim o operaţie asupra unei clădiri ca fiind adăugarea sau scăderea unei unităţi din înalţimea acesteia. Deoarece bugetul primăriei este limitat, primarul doreşte să modifice clădirile în forma dorită cu un număr minim de operaţii. Deoarece doriţi să fiţi făcut cetaţean de onoare al oraşului, voi trebuie să-l ajutaţi pe primar.
h2. Date de intrare
Fişierul de intrare $ktown.in$ ...
Pe prima linie a fişierului ktown.in se află $N$ şi $K$, numărul de clădiri din Tecuci, respectiv diferenţa minimă dintre o clădire şi cea din stânga sa. Următoarea linie conţine $N$ numere întregi, al $i$-lea din aceste numere reprezentând înălţimea celei de-a $i$-a clădiri.
h2. Date de ieşire
În fişierul de ieşire $ktown.out$ ...
Pe prima (şi singura) linie a fişierului ktown.out trebuie să afişaţi numărul minim de operaţii necesare pentru a modifică înalţimile clădirilor astfel încât să respecte proprietăţile cerute.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 3.000$
* $1 ≤ K ≤ 1.000.000$
* $-2.200.000.000 ≤ înălţimea unei clădiri ≤ 2.200.000.000$
* Pentru $60%$ din teste $N ≤ 300$
* Valoarea lui $K$ a fost stabilită de cercetătorii de la Universitatea Naţională din Tecuci, după lungi dezbateri
h2. Exemplu
table(example). |_. ktown.in |_. ktown.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 1
5 4 3 2 1
| 12
|
h3. Explicaţie
...
Vom aduce clădirea $1$ la înălţimea $1$ (cu costul $4$), clădirea $2$ la înălţimea $2$ (cu costul $2$), clădirea $3$ la înalţimea $3$ (cu costul $0$), clădirea $4$ la înălţimea $4$ (cu costul $2$) şi clădirea $5$ la înălţimea $5$ (cu costul $4$).
== include(page="template/taskfooter" task_id="ktown") ==
== include(page="template/taskfooter" task_id="ktown") ==
