Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | echipe.in, echipe.out | Sursă | .campion 2005 |
| Autor | Mugurel Ionut Andreica | Adăugată de | |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |  5/5 |
Vezi solutiile trimise | Statistici
Echipe
| Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata. Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii. |
|---|
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
S 1 <= K <= N <= 250
S 0 <= A < B <= 1.000.000
S Daca o echipa contine 0 jucatori, durata ei de antrenament este 0.
S 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.
S
Exemplu
| echipe.in | echipe.out | Explicatie |
| 8 4 | 36 | 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). |
| 0 11 | ||
| 0 10 | ||
| 1 11 | ||
| 2 12 | ||
| 3 13 | ||
| 4 14 | ||
| 5 15 | ||
| 19 28 | ||
