Zoznam úloh

5. Tajomná jaskyňa

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.

Úloha

Na začiatku hry Miška nemá žiadne mlsky. Počas hry sa v jaskyni postupne udeje $n$ udalostí dvoch typov:

  • 0 – Miška nájde $x_i$ mlsiek.
  • 1 – Netopierik s roztomilosťou $k_i$ sa priblíži k Miške dostatočne blízko na to, aby ho mohla ochočiť za jednu mlsku. Ak ho neochočí, odletí ešte predtým, než nastane ďalšia udalosť.

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.

Formát vstupu

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:

  • Ak $t_i = 0$, druhé číslo $x_i$ ($0 \leq x_i \leq 10^6$) predstavuje počet mlsiek, ktoré Miška práve našla.
  • Ak $t_i = 1$, druhé číslo $k_i$ ($0 \leq k_i \leq 10^9$) predstavuje roztomilosť netopierika, ktorého vtedy stretla.

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$ -

Formát výstupu

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.

Príklady

Vstup

5
1 7
0 1
1 3
1 2
1 4

Výstup

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.

Vstup

3
0 3
1 5
1 5

Výstup

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.


  1. Bolo to trooošku viac než chvíľa, ale to budeme zanedbávať. ↩

Pre odovzdávanie sa musíš prihlásiť.
Trojsten

Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.

Kontakt
Ďalšie projekty