Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | branza.in, branza.out | Sursă | preONI 2007 Runda Finala |
| Autor | Adrian Vladu | Adăugată de |  Adrian Vladu •azotlichid |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Branza
Taranul s-a plictisit de munca pe camp si a decis sa isi intemeieze o afacere. In acest sens, si-a deschis o fabrica de branza. In urmatoarele N saptamani pretul branzei va fluctua in functie de cerere. Din fericire taranul cunoaste dinainte (nu se stie de unde) care vor fi preturile in saptamanile ce vor urma. El vrea sa isi minimizeze costurile si sa acopere cerinta de branza. Pentru fiecare saptamana el cunoaste costul C pentru a produce un kg de branza si cantitatea P care va fi cumparata.
Taranul poate produce intr-o saptamana orice cantitate de branza. El poate depozita excesul de branza intr-un depozit, dar trebuie sa plateasca S unitati monetare pentru fiecare kg de branza depozitat timp de o saptamana. Branza poate fi depozitata maxim T saptamani inainte sa se strice.
Ajutati taranul sa-si minimizeze costurile.
Date de intrare
Linia 1 : trei numere intregi N, S, T
Urmatoarele linii : Ci Pi
Date de iesire
costul minim pt a satisface cerinta de branza
Restrictii
- 1 ≤ N ≤ 500 000
- 1 ≤ C ≤ 5 000
- 1 ≤ P ≤ 10 000
- 1 ≤ T ≤ 500 000
Exemplu
| branza.in | branza.out |
|---|---|
| 5 10 3 12 1 21 2 27 4 45 5 52 3 | 488 |
Explicatie
...
