== include(page="template/taskheader" task_id="jsched") ==
Pe un procesor trebuie sa se execute $N$ aplicatii, numerotate de la $1$ la $N$. Fiecare aplicatie $i$ are un timp de executie $t(i)$ si o pondere $w(i)$. Aplicatiile vor fi executate pe procesor intr-o ordine oarecare, fara intrerupere. Fie ordinea in care se executa aplicatiile $p(1), ..., p(N)$. Costul asociate aplicatiei $p(i)$ este $C(p(i))=(t(p(1))+...+t(p(i)))*w(p(i))$. Costul total asociat executiei tuturor aplicatiilor este egal cu $C(1)+...+C(N)$. Determinati costul total minim posibil (care, evident, depinde de ordinea aleasa pentru a executa aplicatiile).
Poveste şi cerinţă...
h2. Date de intrare
Fişierul de intrare $jsched.in$ contine pe prima linie numarul natural $N$. A $i$-a din urmatoarele $N$ linii contine $2$ numere naturale: $t(i)$ si $w(i)$, separate printr-un spatiu.
Fişierul de intrare $jsched.in$ ...
h2. Date de ieşire
În fişierul de ieşire $jsched.out$ veti afisa costul total minim posibil.
În fişierul de ieşire $jsched.out$ ...
h2. Restricţii
* $1 ≤ N ≤ 100.000$
* $1 ≤ t(i) ≤ 1.000$
* $1 ≤ w(i) ≤ 1.000$
* *Aceasta problema are testele impartite in 2 grupe, valorand 30 si, respectiv, 70 de puncte.*
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. jsched.in |_. jsched.out |
|3
2 4
5 2
1 7
|35
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
Aplicatiile vor fi executate in ordinea $3, 1, 2$. Vom avea $C(3)=1*7=7$, $C(1)=3*4=12$ si $C(2)=8*2=16$. Costul total este $7+12+16=35$.
...
== include(page="template/taskfooter" task_id="jsched") ==
