Fişierul intrare/ieşire:echipe.in, echipe.outSursă.campion 2005
AutorMugurel Ionut AndreicaAdăugată de
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Echipe

FC Campion Romania se pregateste pentru finala Ligii Campionilor Europeni. Pentru aceasta, cei N jucatori ai sai se antreneaza zilnic. Pentru fiecare dintre ei se cunoaste intervalul [T1,T2) cand este prezent la antrenament. Pentru ca antrenamentul sa fie mai eficient, jucatorii nu se antreneaza toti la un loc, ci sunt impartiti in K echipe. Fiecare jucator face parte din exact o echipa, dar este posibil ca din unele echipe sa nu faca parte nici un jucator. Deoarece munca in echipa este foarte importanta, antrenamentul fiecareia dintre cele K echipe se poate desfasura numai daca sunt prezenti toti jucatorii care fac parte din acea echipa. In aceste conditii, durata de antrenament a fiecarei echipe este egala cu lungimea intervalului de timp in care sunt prezenti la antrenament toti jucatorii din echipa respectiva. Intrucat finala se apropie, conducerea clubului doreste ca suma duratelor de antrenament ale fiecarei echipe sa fie maxima.

Cerinta

Determinati o impartire in K echipe a celor N jucatori, astfel incat suma duratelor de antrenament sa fie maxima.

Date de intrare

Pe prima linie a fisierului echipe.in se afla doua numere intregi, separate prin spatii: N si K. Pe urmatoarele N linii se afla cate doua numere intregi separate prin spatii, A si B, reprezentand intervalele de timp in care sunt prezenti jucatorii la antrenament.

Date de iesire

In fisierul echipe.out veti afisa suma maxima a duratelor de antrenament corespunzatoare unei impartiri pe echipe optime.

Restrictii si precizari

  • 1 ≤ K ≤ N ≤ 250
  • 0 ≤ A < B ≤ 1.000.000
  • Daca o echipa contine 0 jucatori, durata ei de antrenament este 0.
  • Daca nu exista nici un moment in care toti jucatorii unei echipe sa fie prezenti simultan la antrenament, atunci durata de pregatire a echipei respective este 0.

Exemplu

echipe.inechipe.out
8 4
0 11
0 10
1 11
2 12
3 13
4 14
5 15
19 28
36

Explicatie

Din prima echipa fac parte jucatorii 1, 2 si 3. Din a doua echipa vor face parte jucatorii 4 si 5. Din a treia echipa fac parte jucatorii 6 si 7, iar a patra echipa il va contine doar pe jucatorul 8. Intervalele de antrenament pentru fiecare din cele 4 echipe sunt: [1,10), [3,12), [5,14), [19,28).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content