== include(page="template/taskheader" task_id="ktown") ==
Î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.
Poveste şi cerinţă...
h2. Date de intrare
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.
Fişierul de intrare $ktown.in$ ...
h2. Date de ieşire
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.
În fişierul de ieşire $ktown.out$ ...
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 |
| 5 1
5 4 3 2 1
| 12
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
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") ==
