Fişierul intrare/ieşire:orase1.in, orase1.outSursăLot Vaslui 2014 - Baraj 3 Juniori
AutorIonel-Vasile Pit-Rada, Mihail-Cosmin Pit-RadaAdăugată deAlexandruValeanuAlexandru Valeanu AlexandruValeanu
Timp execuţie pe test0.125 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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ă.

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.

Date de ieşire

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.

Restricţii

  • 2 ≤ N ≤ 106
  • 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

Exemplu

orase1.inorase1.out
7 3
3 1 4 14 4 3
4 2

Explicaţie

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?