Jsched

jsched

== 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") ==

3981