split2

Split2

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

Poveste şi cerinţă...

Se da un sir $V$ cu $N$ numere naturale. Se doreste impartirea acestuia in $M$ subsecvente de lungime para. Costul unei subsecvente este egal cu maximul dintre suma elementelor din prima jumatate si suma celor din a doua jumatate a subsecventei. Costul total al unei impartiri este egal cu costul maxim al unei subsecvente.
 
Sa se calculeze costul total minim care poate fi obtinut prin impartirea sirului $V$.

h2. Date de intrare

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

Fişierul de intrare $split2.in$ contine pe prima linie $T$, numarul de teste. In continuare, fiecare test contine 2 linii. Pe prima din ele se afla $N$ si $M$. Pe cea de a doua linie se afla cele $N$ numere ale sirului $V$.

h2. Date de ieşire

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

În fişierul de ieşire $split2.out$ se va scrie pe cate o linie rezultatul cerut pentru fiecare din cele T teste.

h2. Restricţii

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

* $1 ≤ T ≤ 50$
* $1 ≤ M ≤ N ≤ 1000$
* $1 ≤ V[i] ≤ 10000$
* $N este par.$
* Se garanteaza ca exista o impartire in M intervale

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

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

| 1
10 3
1 2 4 2 4 5 2 2 1 3
| 6

|
h3. Explicaţie

...

1 2 4 2 | 4 5 | 2 2 1 3
 
Prima subsecventa 1 2 4 2 are costul 6.
A doua subsecventa 4 5 are costul 5.
A treia subsecventa 2 2 1 3 are costul 4.

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

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

9414