== include(page="template/taskheader" task_id="orase1") ==
Poveste și cerință...
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
Fișierul de intrare $orase1.in$ ...
Î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
În fișierul de ieșire $orase1.out$ ...
Fișierul $orase1.out$ va trebui să conțină pe o singură linie, separate prin spațiu, două numere naturale, reprezentând distanța maximă corespunzătoare unei amplasări optime a centrelor, respectiv numărul orașelor ce trebuie promovate.
h2. Restricții
* $... ≤ ... ≤ ...$
* $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$
h2. Exemplu
table(example).
|_. orase1.in |_. orase1.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 7 3
3 1 4 14 4 3
| 4 2
|
h3. Explicație
...
O posibilitate de amplasare optimă a centrelor poate fi în orașele $3$ și [$6$].
== include(page="template/taskfooter" task_id="orase1") ==
