Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | peru.in, peru.out | Sursă | RMI 2020 Ziua 1 |
| Autor | Alexandru Petrescu | Adăugată de |  Mihai-Cristian Popescu •mihai50000 |
| Timp execuţie pe test | 0.55 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Peru
Sunt N gandaci in linie (atentie, nu cerc). Gandacul i are o carapace de rezistenta R[i].
Ai o manusa pe care o poti folosi pentru a lovi K gandaci consecutivi deodata, la orice pozitie vrei, de cate ori vrei.
Atunci cand depui efortul E, toti gandacii cu rezistenta mai mica de E sunt striviti, iar ceilalti nu patesc NIMIC. Efortul poate fi diferit de la o lovitura la alta. Se dau T astfel de scenarii. Pentru fiecare scenariu, care e efortul total minim pentru a strivi toti gandacii?
Date de intrare
Fişierul de intrare peru.in contine pe prima linie T, numarul de gandaci.
Urmatoarele 2 * T linii contin descrierea testelor, cate doua linii pentru fiecare test:
Prima linie contine N si K, iar a doua linie contine vectorul R de lungime N.
Date de ieşire
În fişierul de ieşire peru.out contine T linii, pe linia i aflandu-se raspunsul pentru al i-lea test.
Restricţii
- 1 ≤ T, suma N-urilor, K ≤ 106
- Pentru 20% din punctaj 1 ≤ suma N-urilor ≤ 5000
- Pentru 40% din punctaj 1 ≤ suma N-urilor ≤ 105
- Parsati intrarea
O(N) 100p
O(Nlog) 60p
O(NK) 20p
Exemplu
| peru.in | peru.out |
|---|---|
| 3 7 1 1 2 3 2 1 1 5 2 3 2 3 2 5 1 3 1 3 1 | 5 6 5 |
Explicaţie
...
