Fişierul intrare/ieşire:ambuscada.in, ambuscada.outSursăAlgoritmiada 2009, Runda Finala
AutorAdrian AirineiAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.3 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Ambuscada

Generalul sef Andrei are la dispozitie o armata formata din N soldati si planuieste o ambuscada in vederea cuceririi unor obiective strategice. Pentru fiecare soldat se cunosc Ci, capacitatea de efort a acestuia si Ti, timpul exprimat in minute in care un soldat isi poate folosi toata capacitatea de efort. Andrei a primit de la superiorii sai o lista cu P obiective, pentru fiecare obiectiv cunoscandu-se Di, gradul de dificultate care il presupune atacarea lui. Generalul Andrei a primit de asemenea si alte indicatii precise. El poate trimite in ambuscada un grup format din exact K soldati. Un grup de soldati poate cuceri un obiectiv daca suma capacitatilor de efort a soldatilor este mai mare sau egala cu gradul de dificultate al obiectivului. Deoarece o data ce si-a utilizat capacitatea de efort un soldat este prea obosit pentru a mai efectua alte actiuni, timpul in care un grup de soldati cucereste un obiectiv reprezinta timpul maxim in care un soldat din grup isi foloseste capacitatea de efort. Acestea fiind spuse, Andrei va roaga sa ii raspundeti la M intrebari primite de la comandantul sef. Comandantul sef i-a pus M intrebari, a i-a intrebare fiind de tipul "care este dificultatea cea mai ridicata a unui obiectiv care se poate cuceri in cel mult Xi minute?".

Date de intrare

Fişierul de intrare ambuscada.in contine pe prima linie patru numere naturale, N K M si P, avand semnificatia din enunt. Pe urmatoarele N linii se afla cate doua numere naturale, Ci si Ti, avand semnificatia din enunt. Pe cea de-a N+2-a linie se afla P numere naturale reprezentand gradele de dificultate ale obiectivelor. Urmeaza apoi M linii, pe fiecare linie aflandu-se cate un numar natural Xi, reprezentand intrebarile puse de comandantul sef.

Date de ieşire

În fişierul de ieşire ambuscada.out se vor afla M linii, pe fiecare linie aflandu-se raspunsul la cate o intrebare pusa de comandant. Daca nu exista niciun obiectiv care sa poata fi cucerit de un grup format din exact K soldati, se va afisa -1, altfel se va afisa dificultatea maxima a unui obiectiv care poate fi cucerit.

Restricţii

  • 1 ≤ N, K, M, P ≤ 100 000
  • 1 ≤ Ci, Ti, Xi ≤ 500 000
  • 1 ≤ Di ≤ 1012
  • Datorita faptului ca soldatii au personalitate, nu exista doi soldati i si j diferiti pentru care Ci = Cj sau Ti = Tj.

Exemplu

ambuscada.inambuscada.out
3 2 4 3
2 1
3 2
4 3
4 6 5
1
2
3
4
-1
5
6
6

Explicaţie

Nu poate cuceri niciun obiectiv intr-un timp de 1 minut deoarece are doar un singur soldat disponibil si trebuie sa trimita un grup format din exact 2 soldati in ambuscada. Poate trimite soldatii 1 si 2 pentru a cuceri obiectivul de dificultate 5 in 2 minute, respectiv soldatii 2 si 3 pentru a cuceri obiectivul de dificultate 6 in 3 minute.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content