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.
daca sirul e d1, d2, ..., dn, raspunsul se calculeaza asa:
int ans = 0; for (int i = 1; i <= n; i++) ans = (23LL * ans + di) % 1000000007.
Restricţii
- 1 ≤ T, suma N-urilor, K ≤ 106
- Pentru 20% din punctaj 1 ≤ suma N-urilor ≤ 5000
- Pentru 50% din punctaj 1 ≤ suma N-urilor ≤ 105
- Parsati intrarea
O(N) 100p
O(Nlog) 50p
O(NK) 20p
Exemplu
| peru.in | peru.out | Explicatie |
|---|---|---|
| 5 7 4 6 6 12 12 8 1 4 7 3 1 1 2 3 2 1 1 5 3 2 3 2 3 2 5 3 1 3 1 3 1 16 7 1 2 3 4 5 6 7 14 12 10 8 6 4 7 1 9 | 930347444 155082818 597891 318026 731832314 | 6 6 12 12 18 18 20 1 1 2 4 4 5 5 2 3 3 5 6 1 3 3 4 5 1 2 3 4 5 6 7 15 16 17 18 19 20 21 22 26 |
