Miškin počítač už má svoje roky a začalo jej vadiť, že je strašne pomalý. Preto sa rozhodla zaobstarať si nový a po chvíli1 vyberania si konečne jeden objednala. Hneď ako jej nový počítač doručili, povedala si, že ho rovno otestuje pri hraní svojej obľúbenej hry.
V hre sa Miška nachádza v jaskyni plnej netopierikov. Dajú sa v nej nájsť aj rôzne predmety, vzácne aj menej vzácne, napríklad netopierie mlsky. Sem-tam sa k nej priblíži roztomilý netopierik natoľko, že ho môže nakŕmiť takouto mlskou. Ak to spraví, tak netopierika automaticky ochočí a už navždy bude jej verným domácim maznáčikom. Ak ho však nenakŕmi, netopierik veľmi rýchlo odletí a Miška už nikdy nedostane príležitosť ochočiť si ho.
Miška má veľmi rada netopierikov a chce maximalizovať súčet roztomilostí tých, ktorých ochočí. Rada by preto vedela, aký najväčší súčet roztomilostí mohla v tejto hre získať. Pomôžte jej s tým.
Na začiatku hry Miška nemá žiadne mlsky. Počas hry sa v jaskyni postupne udeje $n$ udalostí dvoch typov:
Zistite, aký najväčší súčet roztomilostí ochočených netopierikov mohla Miška dosiahnuť pri danom priebehu udalostí. Nezabudnite, že Miška dokáže ochočiť netopierika iba vtedy, keď má v čase jeho priblíženia aspoň jednu mlsku, ktorú ochočením spotrebuje.
V prvom riadku vstupu je počet udalostí $n$ ($1 \leq n \leq 2 \times 10^5$).
Nasleduje $n$ riadkov opisujúcich jednotlivé udalosti, ktoré číslujeme od 0 po $n - 1$. Každý z týchto riadkov obsahuje dve celé čísla. Prvé číslo $t_i$ označuje typ $i$-tej udalosti:
V jednotlivých sadách platia nasledujúce obmedzenia:
| Sada | $1 \leq n \leq$ | Dodatočné obmedzenia |
|---|---|---|
| 1 | $20$ | Roztomilosti sú najviac $10^6$ ($k_i \leq 10^6$) |
| 2 | $20$ | - |
| 3 | $1\,000$ | Miška nájde všetky mlsky práve v prvej udalosti ($t_i = 0 \iff i = 0$) |
| 4 | $1\,000$ | Roztomilosti sú nerastúce ($i < j \implies k_i \geq k_j$) |
| 5 | $1\,000$ | - |
| 6 | $2\times10^5$ | Miška nájde všetky mlsky práve v prvej udalosti ($t_i = 0 \iff i = 0$) |
| 7 | $2\times10^5$ | Roztomilosti sú nerastúce ($i < j \implies k_i \geq k_j$) |
| 8 | $2\times10^5$ | - |
Vypíšte jeden riadok a v ňom jedno celé číslo: najväčší súčet roztomilostí ochočených netopierikov, ktorý dokáže Miška dosiahnuť.
Upozornenie: Výsledok ani niektoré iné premenné sa nemusia zmestiť do 32-bitovej premennej.
5
1 7
0 1
1 3
1 2
1 4
4
Miška počas celej hry našla iba jednu mlsku, preto mohla ochočiť najviac jedného netopierika. Samozrejme si chcela vybrať takého, ktorý mal čo najväčšiu roztomilosť. Netopierika s roztomilosťou 7 však stretla ešte pred nájdením mlsky, preto bol najlepšou možnosťou netopierik s roztomilosťou 4.
3
0 3
1 5
1 5
10
Miška hneď na začiatku našla až tri mlsky, ale stretla iba dvoch netopierikov. Mohla teda ochočiť oboch a dosiahnuť súčet roztomilostí 10.
Bolo to trooošku viac než chvíľa, ale to budeme zanedbávať. ↩
Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.
Trojsten, o.z.
FMFI UK, Mlynská dolina
842 48 Bratislava
Programátorská súťaž pre základoškolákov
Materiály a úlohy na výučbu programovania
Intenzívny programátorský zážitok v lete