| Fişierul intrare/ieşire: | copaci2.in, copaci2.out | Sursă | .campion 2007-2008, Runda 1 |
| Autor | Mircea Bogdan Pasoi | Adăugată de |  Mircea Pasoi •domino |
| Timp execuţie pe test | 0.125 sec | Limită de memorie | 5120 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | copaci2.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.
