orase1

Orase1

== include(page="template/taskheader" task_id="orase1") ==

Pe axa reală există $N$ oraşe, numerotate cu numerele 1, 2, 3, …, $N$. Deşi într-o lume unidimensională lucrurile par a fi mult mai simple, totuşi majoritatea locuitorilor sunt nemulţumiţi de distanţele mari parcurse între oraşe în scopul rezolvării diferitelor probleme. Astfel, pentru o mai bună organizare, s-a supus la vot şi s-a decis promovarea a cel mult $K$ oraşe la rangul de centru adminstrativ. Centrele trebuie amplasate într-un mod isteţ, în aşa fel încât distanţa maximă calculată dintre distanţele de la fiecare oraş la cel mai apropiat centru administrativ să fie cât mai mică. Întrucât costurile de administrare ale unui astfel de centru sunt ridicate, se doreşte să se amplaseze un număr cât mai mic de centre administrative astfel încât distanţa maximă să nu fie modificată.

Pe axa reală există $N$ oraşe, numerotate cu numerele $1, 2, 3, …, N$. Deşi într-o lume unidimensională lucrurile par a fi mult mai simple, totuşi majoritatea locuitorilor sunt nemulţumiţi de distanţele mari parcurse între oraşe în scopul rezolvării diferitelor probleme. Astfel, pentru o mai bună organizare, s-a supus la vot şi s-a decis promovarea a cel mult $K$ oraşe la rangul de centru adminstrativ. Centrele trebuie amplasate într-un mod isteţ, în aşa fel încât distanţa maximă calculată dintre distanţele de la fiecare oraş la cel mai apropiat centru administrativ să fie cât mai mică. Întrucât costurile de administrare ale unui astfel de centru sunt ridicate, se doreşte să se amplaseze un număr cât mai mic de centre administrative astfel încât distanţa maximă să nu fie modificată.

h2. Date de intrare

În fişierul $orase1.in$, pe prima linie se află separate prin spaţii numerele $N$ şi $K$. Pe linia următoare se află $N$ - 1 numere naturale nenule, separate prin spaţii, al i-lea număr reprezentând distanţa dintre oraşele i şi i + 1.

În fişierul $orase1.in$, pe prima linie se află separate prin spaţii numerele $N$ şi $K$. Pe linia următoare se află $N - 1$ numere naturale nenule, separate prin spaţii, al $i$-lea număr reprezentând distanţa dintre oraşele $i$ şi $i + 1$.

h2. Date de ieşire

h2. Restricţii

* $2 ≤ $N$ ≤ 10^6^$
* $1 ≤ $K$ ≤ min(N, 1000)$

* $2 ≤ N ≤ 10^6^$
* $1 ≤ K ≤ min(N, 1000)$

* $suma celor N-1 distanţe nu depăşeşte 2 000 000 000$
* $30% dintre teste vor avea $N$ ≤ 1 000$

h3. Explicaţie

O posibilitate de amplasare optimă a centrelor poate fi în oraşele 3 şi 6.

O posibilitate de amplasare optimă a centrelor poate fi în oraşele $3$ şi $6$.

== include(page="template/taskfooter" task_id="orase1") ==