| Fişierul intrare/ieşire: | secvbest.in, secvbest.out | Sursă | Infoarena Cup 2013 |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Eugenie Daniel Posdarascu •eudanip |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate |   3/5 |
Vezi solutiile trimise | Statistici
Secvbest
Se dau 3 numere naturale N, K, S si un sir de N numere naturale. Acesta trebuie impartit in maxim K subsecvente astfel incat suma costurilor subsecventelor sa fie minima. Costul unei subsecvente este diferenta in modul dintre S si suma elementelor subsecventei.
Date de intrare
Fişierul de intrare secvbest.in va contine pe prima linie 3 numere naturale N, K si S. Pe linia a doua vor fi N numere naturale reprezentand sirul dat.
Date de ieşire
Fişierul de ieşire secvbest.out va contine K valori separate printr-un spatiu. Valoarea i reprezinta costul minim daca sirul trebuie impartit in fix i subsecvente.
Restricţii
- 1 ≤ K ≤ N ≤ 100.000
- 1 ≤ K ≤ 30
- valorile sirului si S vor fi cuprinse in intervalul [1, 1.000.000.000]
Exemplu
| secvbest.in | secvbest.out |
|---|---|
| 5 3 10 5 5 2 9 8 | 19 9 3 |
Trebuie sa te autentifici pentru a trimite solutii. Click aici
