Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | petreceri.in, petreceri.out | Sursă | Summer Challenge 2021 |
| Autor | Alexandru Luchianov, Andrei Robert Ion, Stefan Constantin Piscu | Adăugată de |  comisia summer 2k21 •summer21 |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Petreceri
Dupa cum stiti Rick este un foarte mare iubitor de petreceri. Acesta cand merge la o petrecere mereu isi propune dinainte sa bea cel putin o anumita cantitate de alcool.
Astazi si-a notat, in ordinea in care se intampla, N petreceri pe calendarul sau, fiecare dintre ele cu un numar a[i], numarul de unitati de alcool pe care vrea sa le consume la acea petrecere.
Cand a plecat spre prima dintre ele acesta a realizat ca si-a uitat tot alcoolul in alta dimensiune si tot ce are este sticla lui goala care poate tine T unitati de lichid. Acesta stie ca la fiecare petrecere o unitate de alcool costa c[i] bani (doar nu e prima oara cand a mers acolo) asa ca se intreaba care este numarul minim de bani pe care trebuie sa ii plateasca ca sa isi indeplineaca minimele propuse stiind ca intre petreceri acesta poate cara doar maxim T unitati de alcool in sticla sa.
Date de intrare
Prima linie a fisierului de intrare petreceri.in contine numere N, si T. Pe urmatoarea linie apar N numere, al i-lea dintre ele fiind a[i]. Pe a treia linie apar N numere, al i-lea fiind c[i].
Date de ieşire
Pe prima linie a fisierului petreceri.out se va afisa suma minima de bani care trebuie platita ca Rick sa isi poate indeplini scopurile.
Restricţii
- Rick poate merge la petreceri doar in ordinea data, acesta nevrand sa utilizeze calatoria in timp.
- Rick poate cumpara alcool la inceputul, la finalul, sau oricand in timpul unei petreceri.
- 0 ≤ T ≤ 109
- 0 ≤ N ≤ 106
- 0 ≤ a[i] ≤ T
- 0 ≤ c[i] ≤ 109
- Se garanteaza ca solutia o sa fie mai mica ca 1018
- Pentru teste in valoare de 10 puncte N ≤ 2000
- Pentru alte teste in valoare de 20 de puncte N, T ≤ 2000
- Pentru alte teste in valoare de 30 de puncte N ≤ 200000
- Pentru alte teste in valoare de 40 de puncte nu exista restrictii suplimentare
- ATENŢIE! Avand in vedere testele mari se recomandă parsarea fişierului petreceri.in. Puteţi folosi codul oferit de noi aici (atât pentru utilizatorii de C++ şi sintaxă similară cu fstream, cât şi pentru iubitorii de C pur)
Exemplu
| petreceri.in | petreceri.out |
|---|---|
| 5 2 1 1 1 1 1 1 2 3 4 5 | 8 |
| 10 11 9 5 8 8 9 5 6 7 6 5 6 9 6 9 9 9 5 5 5 7 | 417 |
| 18 19 6 6 8 7 7 8 8 6 8 6 9 9 5 9 9 5 5 9 6 8 7 6 7 7 9 5 7 7 5 8 7 5 5 6 8 7 | 704 |
Explicaţie
La primul exemplu Rick isi va cumpara de la prima petrecere 1 unitate de alcool si o va bea pe loc, si isi va mai cumpara inca 2 la finalul petrecerii pentru a le lua cu el. La a 2-a petrecere va bea o unitate de alcool din sticla si isi va cumpara inca una de la bar. La a treia va face acelasi lucru, plecand cu sticla plina. La ultimele 2 petreceri isi va termina bautura din sticla. Astfel Rick va cumpara 3 unitati de la prima petrecere, una de la a doua petrecere si una de la a treia platind astfel 1+1+1+2+3 = 8 bani.
