CSES - Ositus
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Sinulle on annettu taulukko, jossa on nn positiivista kokonaislukua.

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

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua nn ja kk: taulukon koko ja osituksen koko.

Seuraavalla rivillä on nn kokonaislukua x1,x2,,xnx_1,x_2,\ldots,x_n: taulukon sisältö.

Tuloste

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

Rajat

  • 1n1051 \le n \le 10^5
  • 1kn1 \le k \le n
  • 1xi1091 \le x_i \le 10^9

Esimerkki

Syöte:

5 3
2 4 7 3 5

Tuloste:

8

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