Code Submission Evaluation System Login

Datatähti-valmennus

CSES - Datatähti-valmennus - Ositus

Ositus


View task | Model solution | Statistics


Ositus

Time limit:1.00 s
Memory limit:128 MB

Sinulle on annettu taulukko, jossa on $n$ positiivista kokonaislukua.

Tehtäväsi on osittaa taulukko $k$ väliin niin, että suurin välin summa on mahdollisimman pieni.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $k$: taulukon koko ja osituksen koko.

Seuraavalla rivillä on $n$ kokonaislukua $x_1,x_2,\ldots,x_n$: taulukon sisältö.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: suurin välin summa.

Rajat
Esimerkki

Syöte:
5 3
2 4 7 3 5


Tuloste:
8

Selitys: Paras ositus $3$ osaan on $[2,4],[7],[3,5]$, jossa välien summat ovat $6,7,8$. Suurin summa on viimeisen välin summa $8$.