| Fişierul intrare/ieşire: | niciomare.in, niciomare.out | Sursă | Algoritmiada 2019 Runda Maraton |
| Autor | Tamio-Vesa Nakajima | Adăugată de |  Tamio Vesa Nakajima •tamionv |
| Timp execuţie pe test | 1.5 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Niciomare
Tanaka a decis sa mearga la festivalul NicioMare, tinut in tinutul magic al Tomisului. El acum trebuie sa decida la care dintre DJ sa mearga. La NicioMare vor fi N DJ, cel de al i-lea avand indicele de valoare egal cu vi. Tanaka va urmari cel mult K subsecvente disjuncte de DJ. Din nefericire, daca valoarea totala a unei subsecvente vizionate ar fi prea mare, atunci Tanaka nu ar putea sa aprecieze cum trebuie maretia DJ-ilor. Astfel, fiecare subsecventa urmarita va avea suma indicilor de valoare cel mult S. Tanaka vrea sa se distreze cat mai mult la festival. Dupa cum stim cu totii, te distrezi mai mult daca vezi doi DJ super tari unul dupa celalalt decat daca faci pauza intre. Astfel, Tanaka observa ca daca urmareste o subsecventa de DJ care au suma indicilor de valoare egala cu X, atunci acea subsecventa va contribui cu X2 la distractia lui totala. Ajutati-l pe Tanaka sa selecteze care subsecvente de DJ sa vizioneze astfel incat distractia lui totala sa fie maxima.
In alte cuvinte, selectati cel mult K subsecvente disjuncte din sirul v (care nu trebuie neaparat sa acopere intreg sirul), astfel incat fiecare subsecventa sa aibe suma cel mult S, si suma patratelor sumelor subsecventelor sa fie cat mai mare.
Date de intrare
Fişierul de intrare niciomare.in va contine, pe primul rand, valorile N, K, S.
Pe cel de al doilea rand vor aparea valorile sirului v, in ordine.
Date de ieşire
În fişierul de ieşire niciomare.out se va afisa valoarea ceruta.
Restricţii
- 1 ≤ N ≤ 100.000
- 1 ≤ K ≤ 100
- 1 ≤ S ≤ 100.000.000
- 1 ≤ vi ≤ S
- Pentru 30 de puncte, N ≤ 1.000, K ≤ 10 -- feedback testele 1, 4.
- Pentru alte 30 de puncte, N ≤ 100.000, N * K ≤ 100.000 -- feedback testele 10, 15.
- Pentru alte 10 puncte, N ≤ 100.000, N * K ≤ 1.000.000 -- feedback testele 19, 20.
- Restul testelor de feedback fac parte din testele cele mai mari
Exemplu
| niciomare.in | niciomare.out |
|---|---|
| 10 2 5 1 2 3 4 1 2 3 4 1 2 | 50 |
| 10 5 91 3 8 4 2 3 1 1 5 8 3 | 1444 |
| 10 4 91 6 3 1 3 4 8 8 4 4 2 | 1849 |
| 10 4 97 6 3 4 6 6 7 2 2 2 8 | 2116 |
| 10 5 94 5 5 8 7 2 1 4 1 4 6 | 1849 |
| 100 5 98 3 7 8 5 6 4 2 8 2 6 5 2 5 5 6 5 2 3 2 3 1 2 1 2 7 6 8 4 4 7 7 1 5 1 6 8 1 3 4 5 2 2 4 8 6 1 8 1 4 2 2 8 8 7 7 1 3 3 3 3 4 7 5 6 4 1 3 8 4 8 6 2 7 5 4 8 8 5 8 8 8 6 4 7 8 3 3 4 7 3 3 3 8 8 2 2 2 1 4 2 | 41658 |
| 100 6 99 2 6 6 4 8 5 3 4 88 4 2 7 8 5 6 6 8 7 7 8 7 1 8 6 4 1 8 1 5 4 1 3 6 1 3 1 5 4 4 7 1 6 1 1 5 2 1 2 26 6 1 6 4 8 8 2 2 4 5 8 8 3 6 8 2 8 3 7 1 6 3 4 2 6 3 5 5 5 7 1 1 1 31 6 4 1 3 1 7 2 1 7 8 1 4 4 3 2 4 1 | 49966 |
| 100 8 95 2 3 1 7 5 7 2 3 3 4 6 4 6 5 8 6 3 6 1 1 7 1 8 1 6 4 1 2 7 7 6 7 3 7 2 7 6 5 1 6 5 8 8 3 5 6 5 5 3 7 3 3 5 4 8 7 8 4 4 7 5 4 4 8 6 2 6 8 6 4 3 1 4 3 3 5 4 7 8 6 3 4 6 6 5 4 1 8 5 5 3 6 8 8 2 7 5 7 7 1 | 44621 |
| 100 10 96 1 6 8 2 8 96 7 1 5 8 3 5 3 1 7 2 5 27 4 4 6 4 4 6 4 8 5 7 4 2 8 3 3 1 7 3 6 5 1 8 3 1 7 8 4 6 4 3 1 6 5 2 3 6 8 3 4 2 1 6 8 3 3 5 8 2 1 7 8 3 6 1 6 8 6 1 6 3 7 2 5 5 7 5 3 1 1 4 4 4 7 3 5 4 8 5 4 95 1 6 | 57342 |
Explicatie
Pentru a putea incapea mai bine in pagina, exemplele mari (cu N = 100) au randul al doilea impartit in mai multe bucati; fisierele din input adevarate le vor avea unite pe un singur rand.
