Fişierul intrare/ieşire:kcover.in, kcover.outSursăHappy Coding 2008
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test0.4 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Kcover

Se dau N puncte pe axa OX. Punctele sunt numerotate de la 1 la N, iar punctul i este pozitionat la coordonata xi. Se cere amplasarea pe axa OX a K intervale inchise, astfel incat fiecare din cele N puncte sa fie acoperit de cel putin unul din cele K intervale (un punct i este acoperit de un interval [a,b], daca a≤xi≤b). Se doreste ca suma lungimilor celor K intervale sa fie minima.

Date de intrare

Pe prima linie a fisierului de intrare kcover.in se afla numarul intreg T, reprezentand numarul de teste descrise in continuare. Fiecare test este reprezentat sub forma a 2 linii. Pe prima linie se afla numerele intregi N si K, separate printr-un spatiu. Pe a doua linie se afla coordonatele celor N puncte, separate prin spatii.

Date de iesire

Pentru fiecare din cele T teste din fisierul de intrare, in ordinea in care sunt date in fisier, veti afisa in fisierul de iesire kcover.out cate o linie reprezentand suma minima a lungimilor celor K intervale, astfel incat fiecare punct sa fie acoperit.

Restrictii

  • 1 ≤ T ≤ 10
  • 1 ≤ K ≤ N ≤ 100.000
  • -2.000.000.000 ≤ xi ≤ 2.000.000.000
  • Lungimea unui interval inchis [a,b] este egala cu b-a.

Exemplu

kcover.inkcover.out
6
6 1
2 4 1 8 3 6
6 2
2 4 1 8 3 6
6 3
2 4 1 8 3 6
6 4
2 4 1 8 3 6
6 5
2 4 1 8 3 6
6 6
2 4 1 8 3 6
7
5
3
2
1
0
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?