nikita fish
Ученик
(95),
на голосовании
3 года назад
Петя собирается купить грузовичок и заняться перевозками. Он изучил рынок и выяснил, что в его городе есть n потенциальных клиентов. Для i-го клиента есть mi вариантов контракта. Каждый вариант задается двумя числами: wij — минимальная грузоподъемность грузовика, которая необходима, чтобы выполнить контракт, и cij — прибыль, которую получит Петя, если заключит этот контракт. С каждым клиентом можно заключить не более одного контракта. Сейчас Петя думает, какой грузовик лучше купить, чтобы получить нужную ему прибыль. У него есть q вариантов. В i-м варианте Петя хочет, чтобы его прибыль была не меньше xi . Помогите ему для каждого из вариантов найти минимальную грузоподъемность грузовика, с которой можно получить такую прибыль. Формат входных данных Первая строка содержит число n (1 6 n 6 105 ). Далее следуют n блоков, описывающих варианты контракта для каждого из потенциальных клиентов. Каждый такой блок начинается с числа mi , далее следуют mi пар чисел wij, cij (1 6 mi P , mi 6 5 · 105 , 1 6 wij, cij 6 109 ). Далее следует число q (1 6 q 6 105 ). Далее следуют q чисел xi (1 6 xi 6 109 ). Формат выходных данных Выведите q чисел — минимальную грузоподъемность грузовика, с которой можно получить требуемую прибыль, для каждого из вариантов. Если требуемую прибыль получить невозможно, выведите −1 для соответствующего варианта. Пример работающей программы: https://imgur.com/qr1PCud
его городе есть n потенциальных клиентов. Для i-го клиента есть mi вариантов контракта. Каждый
вариант задается двумя числами: wij — минимальная грузоподъемность грузовика, которая необходима, чтобы выполнить контракт, и cij — прибыль, которую получит Петя, если заключит этот
контракт. С каждым клиентом можно заключить не более одного контракта.
Сейчас Петя думает, какой грузовик лучше купить, чтобы получить нужную ему прибыль. У
него есть q вариантов. В i-м варианте Петя хочет, чтобы его прибыль была не меньше xi
. Помогите
ему для каждого из вариантов найти минимальную грузоподъемность грузовика, с которой можно
получить такую прибыль.
Формат входных данных
Первая строка содержит число n (1 6 n 6 105
).
Далее следуют n блоков, описывающих варианты контракта для каждого из потенциальных
клиентов. Каждый такой блок начинается с числа mi
, далее следуют mi пар чисел wij, cij (1 6 mi
P ,
mi 6 5 · 105
, 1 6 wij, cij 6 109
).
Далее следует число q (1 6 q 6 105
). Далее следуют q чисел xi (1 6 xi 6 109
).
Формат выходных данных
Выведите q чисел — минимальную грузоподъемность грузовика, с которой можно получить требуемую прибыль, для каждого из вариантов. Если требуемую прибыль получить невозможно, выведите −1 для соответствующего варианта.
Пример работающей программы: https://imgur.com/qr1PCud