Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2021-03-18 12:01:35.
Revizia anterioară Revizia următoare

Fişierul intrare/ieşire:	sume3.in, sume3.out	Sursă	utcn-2021
Autor	Tudor Muresan	Adăugată de	Ciprian Oprisa •cypry
Timp execuţie pe test	0.3 sec	Limită de memorie	16384 kbytes
Scorul tău	N/A	Dificultate	N/A

Sume de subsecvențe

Se dă o secvenţă de $n$ întregi pozitivi $A_1, A_2, \ldots, A_n$ , care se împarte în $k \leq n$ subsecvenţe disjuncte $L_1, L_2, \ldots, L_k$ care concatenate dau secvenţa iniţială.

$L_1 = A_1, \ldots, A_{i_1 - 1} \quad\quad L_2 = A_{i_1}, \ldots, A_{i_2 - 1} \quad\quad \ldots \quad\quad L_k = A_{i_{k-1}}, \ldots, A_n$

Se consideră sumele întregilor subsecvenţelor $L_1, L_2, \ldots, L_k$ :

$S_1 = A_1 + \ldots + A_{i_1 - 1} \quad\quad S_2 = A_{i_1} + \ldots + A_{i_2 - 1} \quad\quad \ldots \quad\quad S_k = A_{i_{k-1}} + \ldots + A_n$

Scrieţi un program care să împartă secvenţa de $n$ numere în $k$ subsecvenţe astfel ca valoarea maximă a unei sume $S_j$ , ( $1 \leq j \leq k$ ) să fie minimă (adică $Rezultat = \min \max\limits_{j=1..k} S_j$ dintre toate împărţirile posibile).