Zoznam úloh

7. Čo si dnes kúpi Dalibor

Dalibor, tiež nazývaný Dalyb, je veľký swagger. Každých pár dní musí mať novú designerskú tašku, aby bol jeho outfit dostatočne fly. Akurát aj Dalyb žije v tejto ekonomike a veľkú časť príjmov musí dať na obyčajné smrteľnícke výdavky ako nájom a potraviny. Preto si tašky radšej len požičiava.

Aj tak ale vreckové od jeho rodičov nestačí pre potreby jeho swagu. Rozhodol sa teda hustliť predávaním operačnej pamäte. V RAMSWAGSHOPe vedia oceniť jeho štýl. Každý deň, keď prvýkrát príde s nejakou jeho designerskou taškou, ponúknu mu zadarmo RAMku určitého objemu a určitej hodnoty. Pokiaľ sa mu táto RAMka do tašky zmestí, môže si ju zobrať.

Dalyb už má vyhliadnuté nejaké designerské tašky, ktoré by si chcel požičať. Pre každú vie, kedy si ju plánuje požičať, kedy vrátiť a aký má objem. Pri vrátení dostane toľko peňazí, akú budú mať hodnotu RAMky uložené vo vracanej taške. Samozrejme, musia sa do tašky zmestiť, teda súčet objemov RAMiek v taške nemôže prevyšovať objem tejto tašky. Pomôžte Dalybovi pre každú tašku zistiť, koľko najviac je ňou schopný zarobiť.

Úloha

Máme daných $n$ predmetov, kde každý predmet má svoj objem a hodnotu. Ďalej dostaneme $q$ otázok. $i$-ta z nich určená číslami $l_i, r_i, c_i$. Jej odpoveď je jedno číslo: najväčšia možná hodnota predmetov, ktoré vieme zobrať, ak nemôžu mať objem väčší ako $c_i$ a môžeme brať iba z predmetov, ktoré boli na vstupe uvedené od $l_i$-teho až po $r_i$-ty predmet vrátane.

Formát vstupu

V prvom riadku vstupu je číslo $n$ udávajúce počet predmetov na vstupe. Nasleduje $n$ riadkov. Na každom sú dve čísla $v_i, p_i$ oddelené medzerou, ktoré reprezentujú objem a hodnotu $i$-teho predmetu. Platí, že $1 \leq v_i, p_i \leq 10^9$.

Na ďalšom riadku je číslo $q$ udávajúce počet otázok. Nasleduje $q$ riadkov. Na každom sú tri čísla $l_i, r_i, c_i$, ktorých význam je popísaný vyššie. Platí, že $1 \leq l_i \leq r_i \leq n$ a $1 \leq c_i \leq 500$.

Vstupy sú rozdelené do ôsmich sád. Za každý vyriešenú sadu získa váš program jeden bod. V jednotlivých sadách platia nasledujúce obmedzenia:

Sada 1, 2 3, 4 5, 6 7, 8
$1 \leq n \leq$ $100$ $2\,000$ $2\,000$ $2 \cdot 10^4$
$1 \leq q \leq$ $100$ $5\cdot 10^4$ $5 \cdot 10^4$ $2 \cdot 10^5$

V druhej sade navyše platí, že pre všetky $1 \leq i \leq n$ platí $r_i - l_i \geq \lfloor N / 2 \rfloor$.

Formát výstupu

Vypíšte $q$ riadkov. V $i$-tom z nich bude odpoveď na $i$-tu otázku zo vstupu

Príklady

Vstup

4
5 5
2 4
4 3
3 2
3
1 4 10
1 4 9
2 4 1

Výstup

11
9
0

Tento vstup sa mohol vyskytnúť aj v druhej sade, lebo všetky otázky sa pýtaju na dostatočne veľký podúsek. V prvej otázke je optimálne zobrať prvý, druhý a štvrtý predmet v poradí. V je optimálne zobrať prvý a druhý predmet. V tretej otázke nevieme zobrať žiadny predmet, keďže majú všetky väčší objem ako môžeme zobrať. Odpoveď je teda 0

Vstup

8
145 512438721
31 784215630
219 365190442
87 913726504
42 658341297
268 194827365
176 845613209
24 731905418
8
5 8 150
2 6 100
1 7 300
3 8 250
4 5 130
1 4 220
6 8 400
2 2 50

Výstup

1390246715
1442556927
2543555343
2303973219
1572067801
1697942134
1577518627
784215630
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