Fişierul intrare/ieşire:jsched.in, jsched.outSursăSelectie individuala ACM ICPC, UPB 2009
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test0.075 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.injsched.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content