Fişierul intrare/ieşire:ktown.in, ktown.outSursăLot Baia Mare 2013 - Baraj 3 Seniori
AutorAndrei Ciocan, Andrei ParvuAdăugată deMagnvsDaniel Constantin Anghel Magnvs
Timp execuţie pe test0.2 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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.

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.

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.

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

Exemplu

ktown.inktown.out
5 1
5 4 3 2 1
12

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).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content