Fişierul intrare/ieşire:procesor.in, procesor.outSursăAlgoritmiada 2011, Runda 2
AutorCosmin Silvestru NegruseriAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.6 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Procesor

Aveti la dispozitie un procesor si N procese care trebuie executate pe acest procesor. Timpul de rulare al fiecarui proces este de exact o secunda, iar procesorul poate executa maxim un singur proces in orice moment de timp. Incepand de la momentul de timp zero, voi trebuie sa decideti ce procese vor rula pe procesor si la ce momente de timp. Daca un proces i isi va incepe executia mai tarziu de timpul Ti (la un moment de timp cu o valoare mai mare sau egala decat Ti), atunci va fi aplicata o penalizare Pi. Voi trebuie sa calculati penalizarea totala minima posibila.

Date de intrare

Fişierul de intrare procesor.in va contine pe prima linie numarul natural N, avand semnificatia din enunt. Urmeaza apoi N linii, pe linia i+1 aflandu-se, separate de un singur spatiu, doua valori Ti si Pi.

Date de ieşire

În fişierul de ieşire procesor.out se va afla o singura valoare, penalizarea totala minima posibila.

Restricţii

  • 1 ≤ N ≤ 100 000
  • 1 ≤ Ti ≤ 1 000 000
  • 1 ≤ Pi ≤ 1 000 000 000

Exemplu

procesor.inprocesor.out
3
1 10
1 5
4 4
5

Explicaţie

O solutie posibila este urmatoarea: la momentul de timp 0 incepe executia primul proces. Apoi la momentul de timp 1 isi incepe executia al treilea proces. La momentul de timp 2 incepe executia al doilea proces, pentru care se aplica o penalizare egala cu 5.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content