Fișierul intrare/ieșire orase1.in, orase1.out Sursă Lot Vaslui 2014 - Baraj 3
Autor Ionel-Vasile Piț-Rada | Mihail-Cosmin Piț-Rada Adăugată de avatar TincaMatei Tinca Matei TincaMatei
Timp de execuție pe test 0.5 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate N/A

Orase1 (Lot Juniori)

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.in orase1.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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 1 categorii