Fişierul intrare/ieşire:cascaval.in, cascaval.outSursăHappy Coding 2007
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test1.65 secLimită de memorie67583 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cascaval

O companie producatoare de cascaval (si alte branzeturi) doreste sa isi planifice productia pe urmatoarele N luni. Pentru fiecare luna i, compania cunoaste cererea de cascaval Di, exprimata in kilograme. Se cunoaste, de asemenea, costul pentru a produce Q (Q > 0) kilograme de cascaval in luna i, ca fiind egal cu Fi + Ci*Q (Fi reprezinta costurile fixe, iar Ci reprezinta costurile variabile). Costul pentru a produce 0 kilograme de cascaval este 0. Compania poate sa stocheze o parte din cantitatea de cascaval produsa intr-o anumita luna, pentru a o folosi pentru satisfacerea cererii dintr-o luna ulterioara. Se cunoaste costul stocarii unui kilogram de cascaval in fiecare luna i (pana la inceputul lunii urmatoare), ca fiind Si. Compania doreste sa satisfaca integral cererea din fiecare luna, platind pentru aceasta un cost total cat mai mic. Costul total este egal cu suma costurilor de productie si a costurilor de stocare din fiecare din cele N luni.

Date de intrare

Prima linie a fisierului de intrare cascaval.in contine numarul natural N, reprezentand numarul de luni. A i-a din urmatoarele N linii contine 4 numere intregi, Fi, Ci, Si, si Di, separate prin cate un spatiu, avand semnificatiile precizate in enunt.

Date de iesire

In fisierul de iesire cascaval.out veti afisa costul total minim pe care trebuie sa il plateasca compania pentru a satisface integral cererea de cascaval din fiecare luna.

Restrictii

  • 1 ≤ N ≤ 100 000
  • 0 ≤ Fi ≤ 1 000 000 000
  • 0 ≤ Ci ≤ 1 000 000
  • 0 ≤ Si ≤ 100
  • 0 ≤ Di ≤ 1000
  • Cascavalul poate fi stocat oricat de multe luni (nu se strica).

Exemplu

cascaval.incascaval.out
4
4 3 2 1
3 2 1 4
2 1 4 3
1 4 3 2
32
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content