secvbest

Secvbest

== include(page="template/taskheader" task_id="secvbest") ==

Se da

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.

h2. Date de intrare

Fişierul de intrare $secvbest.in$ ...

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.

h2. Date de ieşire

În fişierul de ieşire $secvbest.out$ ...

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.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ K ≤ N ≤ 100.000$
* $1 ≤ K ≤ 30$
* valorile sirului si $S$ vor fi cuprinse in intervalul $[1, 1.000.000.000]$

h2. Exemplu
table(example). |_. secvbest.in |_. secvbest.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5 3 10
5 5 2 9 8
|19 9 3

|

h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="secvbest") ==