| Fişierul intrare/ieşire: | jsched.in, jsched.out | Sursă | Selectie individuala ACM ICPC, UPB 2009 |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Mugurel-Ionut Andreica •mugurelionut |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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).
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.
Date de ieşire
În fişierul de ieşire jsched.out veti afisa costul total minim posibil.
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.
Exemplu
| jsched.in | jsched.out |
|---|---|
| 3 2 4 5 2 1 7 | 35 |
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.
