Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2013-12-13 17:52:02.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:split2.in, split2.outSursăONIS 2014, Runda 1
AutorCazacu AlexandruAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test0.25 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Split2

Se da un sir V cu N numere intregi. Se doreste impartirea acestuia in M subsecvente de lungime para. Costul unei subsecvente este egal cu maximul dintre suma elementelor din prima jumate 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 optinut prin impartirea sirului V.

Date de intrare

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 intregi ale sirului V.

Date de ieşire

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

Restricţii

  • 1 ≤ T ≤ 50
  • 1 ≤ M ≤ N ≤ 1000
  • 1 ≤ V[i] ≤ 10000
  • N este par

Exemplu

split2.insplit2.out
1
10 3
1 2 4 2 4 5 2 2 1 3
6

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?