| Fişierul intrare/ieşire: | sec.in, sec.out | Sursă | Autumn WarmUp 2019 |
| Autor | Alexandru Petrescu | Adăugată de |  Gavrila Vlad •GavrilaVlad |
| Timp execuţie pe test | 1 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Sec
Henry nu trebuia să fie aici. Se retrăsese în munţi, făcând curăţenie pe plaiuri alpine. Însă Marcel era prea ocupat să scrie poezii pentru fete cu păr mov, iar problema trebuia pregătită, aşa că iată-ne aici:
Se da un sir de N numere intregi. Calculeaza, pentru fiecare subsecventa continua de lungime cel putin K, maximul din secventa. Aduna toate rezultatele si afiseaza suma.
Pentru cerinta C = 1, sirul este circular. Pentru C = 2, sirul este unul obisnuit.
Date de intrare
Fişierul de intrare sec.in contine, pe prima linie, numarele T de teste si C, cerinta. Pentru fiecare test, prima linie contine numerele N si K iar a doua cele N numere intregi.
Se recomanda sa parsati intrarea !
Date de ieşire
În fişierul de ieşire sec.out se vor afla T linii, pe fiecare aflandu-se un singur numar: suma ceruta pentru testul corespunzator.
Restricţii
- Toate numerele din input sunt intregi
- 1 ≤ T ≤ 3
- 1 ≤ C ≤ 2
- 1 ≤ K ≤ N ≤ 2.000.000
- Numerele din sir au valoare absoluta strict mai mica decat 106
Punctare
- Evaluarea se va face pe 10 teste, fiecare valorand cate 10 puncte.
- Testele cu indice impar vor avea C = 1, iar cele cu indice par vor avea C = 2.
- Testul 1 va avea N ≤ 50.
- Testul 2 va avea N ≤ 2.000
- Testele 3, 4 si 5 vor avea N ≤ 100.000.
- Testele 3 si 6 vor avea sirurile de numere generate aleator. Astfel, fiecare valoare din sir va fi aleasa independent de celelalte, cu aceeasi probabilitate sa fie egala cu oricare din numerele intregi din intervalul deschis (-106, 106).
- Testele 7 si 8 vor avea K = 1.
Exemplu
| sec.in | sec.out |
|---|---|
| 3 2 5 3 1 2 3 4 5 4 1 -1 100 -2 -3 2 2 1 1 | 26 592 1 |
| 3 1 10 1 1 10 1 1 10 1 100 1 10 1 10 2 1 10 1 1 10 1 100 1 10 1 10 3 1 10 1 1 10 1 100 1 10 1 | 4978 4842 4580 |
| 3 1 10 4 1 10 1 1 10 1 100 1 10 1 10 5 1 10 1 1 10 1 100 1 10 1 10 6 1 10 1 1 10 1 100 1 10 1 | 4210 3750 3200 |
| 3 1 10 7 1 10 1 1 10 1 100 1 10 1 10 8 1 10 1 1 10 1 100 1 10 1 10 9 1 10 1 1 10 1 100 1 10 1 | 2560 1830 1010 |
| 1 1 10 10 1 10 1 1 10 1 100 1 10 1 | 100 |
