Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | covrigi.in, covrigi.out | Sursă | FMI No Stress 9 |
| Autor | Theodor Moroianu | Adăugată de |  FMI No Stress 9 •fminostress9 |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 16384 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Covrigi
Concursul FMICUSTRESS se desfasoara in Universitatea din Bucuresti. Fiind un concurs deosebit de cunoscut, are si o cantitate deosebita de premii.
Astfel, castigatorul concursului urmeaza sa primeasca un telefon, cel de pe locul 2 un cupon cu 10 beri gratuite la beraria H etc.
Tie nu prea iti pasa de premiu pentru ca oricum urmeaza sa il vinzi pentru a avea bani sa iti cumperi covrigi de la Luca in pauza, asa ca ti-ai construit un vector V, unde V[i] reprezinta castigul tau daca iesi pe pozitia i (cati covrigi Luca o sa poti sa iti cumperi). In mod evident, ca la oricare concurs care se respecta, V[i] ≤ V[i + 1].
Pentru a avea un loc mai bun, ai posibilitatea sa iti cumperi cateva raspberry pi-uri (oricum sunt foarte ieftine), sa le plasezi undeva in universitate, si sa ii "convingi" pe cei din jurul lor sa te lase sa castigi, rasberry pi-urile picandu-le netul (in regulamentul intern al universitatii scrie explicit ca nu patesti nimic pana nu esti prins - ceea ce evident nu o sa fie cazul).
Concret stii ca:
- sunt N concurenti care participa la concurs,
- studentii sunt impartiti in M sali,
- un raspberry pi costa echivalentul a K covrigi Luca,
- cu fiecare raspberry pi poti sa impiedici o unica sala din a participa la concurs.
Ti se dau si cei doi vectori V al castigului in functie de loc, si C, C[i] reprezentand cati concurenti din sala i ar fi clasati mai bine ca tine daca nu i-ai impiedica.
Cati covrigi Luca o sa poti sa iti iei maxim dupa concurs, presupunand ca joci optim?
N, M <= 1.000.000
Date de intrare
Fişierul de intrare covrigi.in contine pe prima linie numerele N, M si K, cu semnificatiile de mai sus.
Urmatoarea linie contine vectorul V de lungime N.
Ultima linie contine vectorul C, de lungime M. Se garanteaza ca suma elementelor din C este mai mica decat N.
Date de ieşire
În fişierul de ieşire covrigi.out contine un singur numar, numarul maxim de covrigi pe care poti sa ii castigi.
Restricţii
- 1 ≤ N, M ≤ 100.000
- Se garanteaza ca inputul este valid (Cel putin un concurent, toate numerele din input sunt pozitive etc)
- Numerele citite din input sunt mai mici decat 231
Exemplu
| covrigi.in | covrigi.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
