Fişierul intrare/ieşire:trans.in, trans.outSursăONI 2004
AutorMugurel Ionut AndreicaAdăugată de
Timp execuţie pe test0.075 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Trans

In depozitul unei companii de constructii se afla N blocuri de piatra, de culoare alba sau neagra. Ele sunt asezate in ordinea 1, 2,.., N, de la intrarea in depozit catre interior. Blocurile de piatra trebuie sa fie transportate pe un santier de constructii, in ordinea in care ele sunt depozitate, iar pentru aceasta va trebui inchiriat un camion de la o companie de transport. Aceasta detine Q tipuri de camioane. Camionul de tipul i (1 ≤ i ≤ Q) poate transporta maxim Ki blocuri de piatra la un moment dat si pentru un transport se percepe taxa Ti.

Compania de transport este de parere ca, pentru a-si pastra clientela, trebuie sa impuna anumite standarde, indiferent de cat de absurde ar fi, deci impune conditia ca toate blocurile de piatra plasate in camion la un transport sa aiba aceeasi culoare. Asadar, pentru a fi transportate toate blocurile pe santier, compania de constructii va alege un camion de un anumit tip, iar camionul va efectua unul sau mai multe transporturi. Pentru a micsora suma totala platita, compania de constructii are posibilitatea de a schimba culoarea oricarui bloc de piatra (din alb in negru sau din negru in alb); pentru fiecare bloc i (1 ≤ i ≤ N) se cunoaste suma Si ce trebuie platita pentru a-i schimba culoarea.

Cerinta

Pentru fiecare dintre cele Q tipuri de camioane detinute de compania de transport, determinati suma minima pe care o va plati compania de constructii pentru a transporta toate cele N blocuri pe santier.

Date de intrare

Fisierul de intrare trans.in contine pe prima linie numarul intreg N, reprezentand numarul de blocuri de piatra din depozit. Pe fiecare dintre urmatoarele N linii se afla informatii referitoare la cate un bloc de piatra. Pe a i-a dintre aceste N linii se gasesc doua numere intregi separate printr-un spatiu: Ci Si, reprezentand culoarea celui de-al i-lea bloc (Ci este 0 pentru alb si 1 pentru negru) si respectiv suma ce trebuie platita pentru a-i schimba culoarea (daca este necesar). Pe urmatoarea linie se afla numarul natural Q, reprezentand numarul de tipuri de camioane detinute de compania de transport. Pe fiecare dintre urmatoarele Q linii se afla informatii referitoare la cate un camion. Pe cea de a i-a dintre aceste Q linii sunt scrise doua numere naturale separate printr-un spatiu Ki Ti, reprezentand numarul maxim de blocuri ce pot fi transportate simultan de catre un camion de tipul i si respectiv taxa ce trebuie platita pentru fiecare transport efectuat.

Date de iesire

Fisierul de iesire trans.out va contine Q linii. Pe cea de a i-a dintre aceste linii va fi afisata suma totala minima platita de compania de constructii pentru a transporta toate cele N blocuri de piatra, in cazul in care ar inchiria un camion de tipul i.

Restrictii si precizari

  • 1 ≤ N ≤ 16 000
  • 1 ≤ Si ≤ 10 000
  • 1 ≤ Q ≤ 100
  • 1 ≤ Ki ≤ N
  • 1 ≤ Ti ≤ 100 000

Exemplu

trans.intrans.out
4
0 2
1 3
0 10
1 2
3
4 1000
4 1
2 5
1005
4
14
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content