Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | peste.in, peste.out | Sursă | preONI 2008, Runda finala |
| Autor | Adrian Airinei | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Peste
Titus merge la pescuit pe malul raului Bahlui, unde isi propune sa stea TTotal minute. El detine N plase de prins peste si fiecare plasa i poate prinde Pi pesti daca este lasata in apa cel putin Ti minute. Daca o plasa i este lasata mai mult de Ti minute in apa, ea nu va prinde mai mult peste, iar daca este lasata mai putin de Ti minute nu va prinde peste deloc. De asemenea, niciodata in apa nu pot fi mai mult de K plase de prins peste. Astfel, Titus incepe pescuitul la momentul de timp 0 (zero) si in orice moment de timp poate face una din urmatoarele actiuni:
- Introduce o plasa de prins peste in apa, numai daca in apa nu sunt deja K plase de prins peste si plasa pe care vrea s-o introduca nu se afla deja in apa
- Scoate o plasa din apa si colecteaza pestii aflati in ea, numai daca toate plasele care sunt in apa au terminat de prins peste (altfel pestii se vor speria si nu va mai prinde nimic)
Cosideram ca ambele actiuni se realizeaza instantaneu (nu consuma nicio unitate de timp), deci la un moment de timp Titus poate realiza oricare din cele doua actiuni de mai multe ori. Aflati pentru Titus care este numarul maxim de pesti pe care il poate prinde in TTotal minute.
Date de intrare
Fisierul de intrare peste.in contine pe prima linie, separate printr-un spatiu, numerele naturale N, K si TTotal, avand semnificatia din enunt. Pe urmatoarele N linii se afla informatii despre plasele de prins peste, pe linia i+1 aflandu-se Pi si Ti, reprezentand informatiile pentru plasa i.
Date de iesire
In fisierul de iesire peste.out se afla pe prima linie numarul natural Res, reprezentand numarul maxim de pesti pe care Titus ii poate prinde in TTotal minute.
Restrictii
- 1 ≤ K, N, TTotal ≤ 50 000
- 1 ≤ Pi, Ti ≤ 1000
Exemplu
| peste.in | peste.out |
|---|---|
| 3 2 5 10 5 2 4 1 3 | 12 |
Explicatie
O solutie posibila e urmatoarea: la momentul 0 introduce prima plasa, la momentul 1 introduce a doua plasa, la momentul 5 ambele plase au terminat de prins peste, deci poate scoate intai prima plasa, colecteaza pestii din ea, apoi face acelasi lucru pentru a doua plasa (amintim ca aceste actiuni se realizeaza instant), prinzand in total 12 pesti.
