Rezolvare PBinfo #134

Se dă un șir cu n numere naturale și un număr k.

Cerinţa

Să se determine o secvență de elemente de lungime k cu suma elementelor maximă.

Date de intrare

Fişierul de intrare secvk.in conţine pe prima linie numerele n și k, iar pe a doua linie n numere naturale separate prin spaţii.

Date de ieşire

Fişierul de ieşire secvk.out va conţine pe prima linie k numere, reprezentând elementele secvenței cerute.

Restricţii şi precizări

• 1 ≤ k ≤ n ≤ 100.000
• numerele de pe a doua linie a fişierului de intrare vor fi mai mici decât 1000
• dacă există mai multe secvențe de lungime k cu suma maximă se va afișa prima

Exemplu:

secvk.in

8 3
5 6 1 2 6 6 4 3

secvk.out

6 6 4

Explicație

Sumele care se pot obține sunt: 12 9 9 14 16 13. Suma maximă este 16 și se obține pentru secvența 6 6 4