Fişierul intrare/ieşire:vrejuri.in, vrejuri.outSursăAlgoritmiada 2010, Runda 1
AutorCosmin GheorgheAdăugată degcosminGheorghe Cosmin gcosmin
Timp execuţie pe test0.075 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Vrejuri

Ofelia are in gradina N vrejuri magice, fiecare avand o anumita inaltime Hi. Problema este ca vrejurile au inceput sa creasca, astfel, fiecare planta i isi va mari inaltimea cu Pi zilnic. Ofelia stie ca vrejurile vor creste doar in urmatoarele K zile iar dupa aceea se vor opri, si vrea ca la sfarsitul celor K zile suma inaltimilor tuturor vrejurilor sa fie cel mult S. Pentru aceasta, ea are o foarfeca magica cu ajutorul careia, la sfarsitul fiecarei zile, poate reduce inaltimea fiecarui vrej i cu xi. Dar foarfeca magica nu este usor de folosit, astfel pentru a taia o anumita valoare xi din vrejul i efortul depus este xi2 Jouli (Ofelia se pricepe la fizica, dar, bineinteles, nu si la informatica). Ofelia vrea sa afle care este efortul total minim J (suma tuturor eforturilor depuse in procesele de taiere), pe care il poate depune pentru ca suma inaltimilor vrejurilor la sfarsitul celor K zile sa fie cel mult S.

Date de intrare

Fişierul de intrare vrejuri.in va contine pe prima linie numerele N, K si S. Urmatoarele N linii vor contine fiecare cate doua numere Hi si Pi reprezentand inaltimea initiala a vrejului i si respectiv, rata cu care acesta creste.

Date de ieşire

În fişierul de ieşire vrejuri.out veti afisa un singur numar J efortul minim pe care Ofelia il poate depune.

Restricţii

  • 1 ≤ N, K ≤ 100 000
  • 0 ≤ S ≤ 1018
  • 1 ≤ Hi, Pi ≤ 109
  • Se garanteaza ca rezultatul J nu va depasi 1018
  • Se garanteaza ca suma inaltimilor tuturor vrejurilor netaiate la sfarsitul celor K zile nu va depasi 1018
  • Atentie: Ofelia poate taia doar dupa ce prima zi se incheie. Adica vrejurile cresc in prima zi si abia apoi Ofelia poate taia din ele
  • Atentie: La sfarsitul fiecarei zile Ofelia poate taia orice valoare din oricate plante. Ea poate taia valori diferite din plante diferite in zile diferite.
  • Chiar daca o planta este taiata pana la inaltimea 0, ea tot va creste in urmatoarea zi (radacina nu se scoate).

Exemplu

vrejuri.invrejuri.out
2 2 1
1 1
2 2
18

Explicaţie

Ofelia poate taia in prima zi 1 din primul vrej si 2 din al doilea, iar in a doua zi 2 din primul si 3 din al doilea. Costul total este 18.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content