| Fişierul intrare/ieşire: | split2.in, split2.out | Sursă | ONIS 2014, Runda 1 |
| Autor | Cazacu Alexandru | Adăugată de |  FMI No Stress •fmins123 |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Split2
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.
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 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.
- Se garanteaza ca exista o impartire in M intervale
Exemplu
| split2.in | split2.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.
