Fişierul intrare/ieşire:niciomare.in, niciomare.outSursăAlgoritmiada 2019 Runda Maraton
AutorTamio-Vesa NakajimaAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test3 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/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.inniciomare.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?