Code Submission Evaluation System Login

IOI-leiri 2016

Koulut


Task | Statistics


CSES - KoulutCSES - Koulut

Time limit:2.00 s Memory limit:512 MB

Tien varrella on $n$ taloa, ja tiedät jokaisesta talosta, montako lasta siinä asuu. Tehtäväsi on perustaa $k$ koulua niin, että jokainen koulu on jossakin talossa ja lasten yhteismatka kouluun on mahdollisimman lyhyt.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $k$: talojen määrä ja koulujen määrä. Talot on numeroitu $1,2,\ldots,n$.

Sitten syötteessä on $n$ kokonaislukua $t_1,t_2,\ldots,t_n$: montako lasta kussakin talossa asuu.

Koulujen perustamisen jälkeen kaikki tietyssä talossa asuvat lapset menevät lähimpään kouluun. Matkan kustannus on lasta kohden $|a-b|$, missä $a$ on talon numero ja $b$ on koulun numero.

Tuloste

Tulosta yksi kokonaisluku: pienin mahdollinen kaikkien lasten yhteiskoulumatka.

Rajat
Esimerkki

Syöte:
6 2
2 7 1 4 6 4


Tuloste:
11

Selitys: koulut perustetaan taloihin 2 ja 5.