Fişierul intrare/ieşire:sume3.in, sume3.outSursăutcn-2021
AutorTudor MuresanAdăugată decypryCiprian Oprisa •cypry
Timp execuţie pe test0.3 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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 L_2 = A_{i_1}, \ldots, A_{i_2 - 1} \quad \ldots \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 S_2 = A_{i_1} + \ldots + A_{i_2 - 1} \quad \ldots \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).

Date de intrare

Fişierul de intrare sume3.in conţine mai multe exemple de test. Un exemplu are pe prima linie doi întregi n, k separaţi de un spaţiu determinând numărul n al întregilor secvenţei şi numărul k al subsecvenţelor. Pe linia următoare se dau cei n întregi A_i separaţi de un spaţiu. Fişierul se termină cu o linie conţinând un 0.

Date de ieşire

Fişierul de ieşire sume3.out conţine câte o linie pentru fiecare exemplu de test, pe care se tipăreşte numărul exemplului de test urmat de ':' şi de cea mai mică valoare maximă a sumei unei subsecvenţe posibil a fi obţinută la o împărţire a secvenţei date.

Restricţii

  • 1 \leq k \leq n \leq 500
  • 1 \leq A_i \leq 10^6, \forall i \in \lbrace 1, \ldots, n \rbrace

Exemplu

sume3.insume3.out
5 3
1 2 3 4 5
3 2
4 78 9
0
1:6
2:82
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?