V obchode s úlohami pripravujú akciu, kúp 5 a 2 najlacnejšie dostaneš zadarmo. Alebo to malo byť kúp 8 a 3 dostaneš zadarmo? Problém je, že táto akcia sa stratila a nikto teraz nevie aké čísla tam boli. Vedúci prevádzky potrebuje teda vymyslieť aké čísla budú v akcii. Najprv by ale chcel vedieť, koľko najviac potom bude môcť stratiť na jednom nákupe.
Na vstupe dostanete zoznam cien produktov ktoré obchod predáva a niekoľko otázok v tvare $a b$, teda aká môže byť najväčšia cena vecí ktoré dostane zákazník zadarmo, ak bude akcia “Kúp $a$ a $b$ najlacnejších dostaneš zadarmo”. Každý predmet v obchode si môže zákazník kúpiť len raz.
V prvom riadku vstupu sú číslo $n$ a $q$ ($1 \leq n, q \leq 10^6$) udávajúce počet predmetov v obchode a počet otázok. V druhom riadku je $n$ medzerou oddelených čísel $c_i$ ($1 \leq c_i \leq 10^6$) udávajúce ceny predmetov. Nasleduje $q$ riadkov pri čom na $i$-tom sa nachádzajú medzerou oddelené čísla $a_i$ a $b_i$ ($1 \leq b_i \leq a_i \leq n$).
Vypíš $q$ riadkov, na $i$-tom z nich jedno celé číslo a to odpoveď na $i$-tu otázku.
5 3
5 3 1 5 2
3 2
1 1
5 3
8
5
6
V prvej otázke môžeme kúpiť predmety s cenou $5$, $3$ a $5$, dva najlacnejšie z nich stoja spolu $3+5=8$. V druhej otázke kupujeme len jeden predmet a je zadarmo, teda môžeme kúpiť predmet s cenou $5$. V poslednej otázke kupujeme všetky predmety a zadarmo sú tri najlacnejšie, teda $1+2+3=6$.
Podľa zadania dostaneme zadarmo $b$ najlacnejších predmetov ak kúpime aspoň $a$ predmetov. Ľahko si môžeme uvedomiť, že sa nám oplatí kúpiť presne $a$ predmetov a to konkrétne $a$ nájdrahších predmetov. V takom prípade budú mať tie najlacnejšie z nich najväčšiu cenu. Prvým krokom je teda postupnosť zoradiť od najdrahšieho po najlacnejší predmet.
Ak už máme postupnosť zoradenú, stačí nám pre každú otázku spočítať súčet od $a-b$-teho po $a$-ty predmet a to je naša odpoveď.
N, q = map(int,input().split())
predmety = list(map(int,input().split()))
predmety.sort()
predmety.reverse()
for i in range(q):
a, b = map(int,input().split())
print(sum(predmety[a - b:a]))
Ku vzorovému riešeniu už stačí iba pridať Prefixové súčty. Viac o tom ako to funguje si môžeš prečítať v našej novej KSP School.
N, q = map(int,input().split())
predmety = list(map(int,input().split()))
predmety.sort()
predmety.reverse()
prefixy = [0]
for i in range(N):
p = prefixy[-1] + predmety[i]
prefixy.append(p)
for i in range(q):
a, b = map(int,input().split())
print(prefixy[a] - prefixy[a - b])