Fişierul intrare/ieşire:copaci2.in, copaci2.outSursă.campion 2007-2008, Runda 1
AutorMircea Bogdan PasoiAdăugată dedominoMircea Pasoi domino
Timp execuţie pe test0.125 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Copaci 2

Zaharel are N copaci in gradina din spatele casei sale, asezati in linie, numerotati convenabil de la stanga la dreapta cu numere de la 1 la N. Dorind ca gradina lui sa arate cat mai frumos si uniform lui si-a propus sa minimize diferenta maxima intre inaltimile copacilor adiacenti. Copacii nu pot fi mutati din loc, dar inaltimile lor pot fi micsorate sau marite (folosind tehnici moderne de gradinarit). Fiecare copac are o inaltime Hi si un cost Ci de a ii mari sau micsora inaltimea cu o unitate.
Stiind ca are la dispozitie un buget de valoare K determinati valoarea minima pentru diferenta maxima intre inaltimile copacilor adiacenti.

Date de intrare

Pe prima linie a fisierului de intrare copaci2.in sunt scrise cele doua numere naturale N, K, separate prin spatii. Pe urmatoarele N linii se vor scrie cate doua numere naturale Hi, Ci, separate prin spatii.

Date de iesire

Prima linie a fisierului copaci2.out va contine un singur numar natural reprezentand valoarea minima pentru diferenta maxima intre inaltimile copacilor adiacenti.

Restrictii

  • 1 ≤ N ≤ 1.000
  • 1 ≤ K ≤ 109
  • 1 ≤ Hi, Ci ≤ 1.000
  • Un copac poate fi micsorat pana la inaltimea 0

Exemplu

copaci2.incopaci2.out
6 9
8 3
9 2
4 3
7 6
4 2
3 4
2

Explicatie

Se micsoreaza inaltimea copacului 2 cu 2 unitati si se mareste inaltimea copacilor 3 si 5 cu o unitate. Noile inaltimi vor fi 8, 7, 5, 7, 5, 3 si diferenta maxima intre inaltimile copacilor adiacenti este 2. Costul total este 2*2 + 1*3 + 1*2 = 9.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content