concert

Concert

== include(page="template/taskheader" task_id="concert") ==

==Include(page="template/taskheader" task_id="concert")==

Poveste ...

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. Restrictii

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

h2. Date de intrare

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 &le; A{~i~} < B{~i~} &le; 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 |

h2. Date de iesire

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$.

h2. Exemplu

==Include(page="template/taskfooter" task_id="concert")==

| concert.in | concert.out |
| linia1
linia2
linia3
| linia1
linia2
|
== include(page="template/taskfooter" task_id="concert") ==

385