==Include(page="template/taskheader" task_id="concert")==
==Include(page="template/taskheader" task_id="concert")==
Un grup de $N$ artisti a primit invitatii sa cante la un concert. Fiecarui artist i s-a trimis o invitatie pe care acesta era invitat sa cante intre orele $A$ si $B$. Insa organizatorii acestui eveniment au gresit invitatiile si timpurile in care trebuiau sa cante anumiti artisti se suprapuneau. Artistii, fiind renumiti, nu accepta sa cante decat singuri. De asemenea ei cer despagubiri daca li se cere sa inceapa sa cante dupa ora $A+1$ sau sa termine inainte de ora $B$. Un anumit artist poate sa cante doar intre orele $A$ si $B$ de pe invitatie. Unele invitatii pot fi anulate, asa ca unii artisti pot sa nu cante deloc.
h2. Cerinta
Cunoscandu-se intervalele intre care poate sa cante fiecare artist, profitul pe care il aduce fiecare artist pe unitatea de timp si despagubirile cerut in ambele cazuri mentionate mai sus, voi trebuie sa aflati care este suma maxima care poate fi obtinuta in concertul respectiv, si cum poate fi ea obtinuta.
h2. Date de Intrare
Pe prima linie a fisierul $concert.in$ se va afla $N$. Pe urmatoarele $N$ linii ale fisierulul se vor gasi cate 5 numere separate prin cate un spatiu. Ele reprezinta $A$, $B$, profitul pe unitatea de timp si despagubirile in cazul in care artistul nu incepe sa cante in $A+1$ si respectiv daca nu termina de cantat in $B$.
h2. Date de Iesire
Pe prima linie a fisierul $concert.out$ se va afla suma maxima care poate fi obtinuta din concert.
h2. Restrictii
* $1 ≤ N ≤ 1.000$
* $1 ≤ A{~i~} < B{~i~} ≤ 2.000.000.000$
* profitul adus de fiecare artist sau despagubirile cerute de fiecare dintre ei nu vor trece de valoare 500. Despagubirile se platesc o data, nu pe unitate de timp.
* daca artistul $i$ are in contract intervalul $(A{~i~},B{~i~})$ el poate canta intre momentele $A{~i~}+1$ si $B{~i~}$ inclusiv.
* oricare doi artisti au intervalele diferite
* solutia nu va trece de valoare 2^31^-1
* Nu exista 2 artisti $x$ si $y$ astfel incat intervalul in care poate canta $x$ sa fie complet inclus in intervalul lui $y$
h2. Exemple
table(example). |_. concert.in |_. concert.out |
| 5
0 5 10 10 15
3 8 8 8 20
4 10 12 4 10
8 16 7 4 7
12 20 10 5 50 | 189 |
h3. Explicatie
Artistul $1$ canta intre orele $1$ si $5$, aducand un profit de $(5-1+1)*10 = 50$ si nu cere despagubiri, pentru ca a cantat intre orele stabilite in invitatie. Artistul $2$ nu canta de loc. Artistul $3$ canta intre orele $6$ si $10$, aducand un profit de $(10-6+1)*12 = 60$, insa i se platesc despagubiri in valoare de $4$, pentru ca nu a inceput la ora la care i s-a spus in invitatie ca va incepe, ora $A+1 = 4$. Astfel artistul $3$ aduce un profit de $60-4 = 56$. Artistul $4$ canta intre orele $11$ si $12$. Aducand un profit de $2*7 = 14$, insa cere ambele despagubiri deci aduca un profit de $14-7-4 = 3$. Artistul cu numarul $5$ aduce un profitde $8*10 = 80$, si nu cere despagubiri, pentru ca a cantat intre orele stabilite. Astfel, totalul se ridica la: $50+56+3+80=189$.
==Include(page="template/taskfooter" task_id="concert")==
==Include(page="template/raw")==
Link: [1]File-List
concert
Un grup de N artisti a primit invitatii sa cante la un concert. Fiecarui artist i s-a trimis o invitatie pe care acesta era invitat sa cante intre orele A si B. Insa organizatorii acestui eveniment au gresit invitatiile si timpurile in care trebuiau sa cante anumiti artisti se suprapuneau. Artistii, fiind renumiti, nu accepta sa cante decat singuri. De asemenea ei cer despagubiri daca li se cere sa inceapa sa cante dupa ora A+1 sau sa termine inainte de ora B. Un anumit artist poate sa cante doar intre orele A si B de pe invitatie. Unele invitatii pot fi anulate, asa ca unii artisti pot sa nu cante deloc.
h2. Cerinta
Cunoscandu-se intervalele intre care poate sa cante fiecare artist, profitul pe care il aduce fiecare artist pe unitatea de timp si despagubirile cerut in ambele cazuri mentionate mai sus, voi trebuie sa aflati care este suma maxima care poate fi obtinuta in concertul respectiv, si cum poate fi ea obtinuta.
h2. Date de Intrare
Pe prima linie a fisierul concert.in se va afla N.
Pe urmatoarele N linii ale fisierulul se vor gasi cate 5 numere separate pin cate un spatiu. Ele reprezinta A, B, profitul pe unitatea de timp si despagubirile in cazul in care artistul nu incepe sa cante in A+1 si respectiv daca nu termina de cantat in B.
h2. Date de Iesire
Pe prima linie a fisierul concert.out se va afla suma maxima care poate fi obtinuta din concert.
h2. Restrictii
S 1 <= N <= 1.000
S 1 <= A[i] < B[i] <= 2.000.000.000
S profitul adus de fiecare artist sau despagubirile cerute de fiecare dintre ei nu vor trece de valoare 500. Despagubirile se platesc o data, nu pe unitate de timp.
S daca artistul i are in contract intervalul (A[i],B[i]) el poate canta intre momentele A[i]+1 si B[i] inclusiv.
S oricare doi artisti au intervalele diferite
S solutia nu va trece de valoare 2^31-1
Exemple
concert.in concert.out
5 189
0 5 10 10 15
3 8 8 8 20
4 10 12 4 10
8 16 7 4 7
12 20 10 5 50
Explicatie: Artistul 1 canta intre orele 1 si 5, aducand un profit de (5-1+1)*10 = 50 si nu cere despagubiri, pentru ca a cantat intre orele stabilite in invitatie. Artistul 2 nu canta de loc. Artistul 3 canta intre orele 6 si 10, aducand un profit de (10-6+1)*12 = 60, insa i se platesc despagubiri in valoare de 4, pentru ca nu a inceput la ora la care i s-a spus in invitatie ca va incepe, ora A+1 = 4. Astfel artistul 3 aduce un profit de 60-4 = 56. Artistul 4 canta intre orele 11 si 12. Aducand un profit de 2*7 = 14, insa cere ambele despagubiri deci aduca un profit de 14-7-4 = 3. Artistul cu numarul 5 aduce un profitde 8*10 = 80, si nu cere despagubiri, pentru ca a cantat intre orele stabilite. Astfel, totalul se ridica la: 50+56+3+80=189.
References
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/concert/enunt.files/filelist.xml
==Include(page="template/taskfooter" task_id="concert")==
