#2118. 混合果汁
混合果汁
混合果汁
题目描述
第二试混合果汁(juice) IOI 2018 中国国家队选拔赛暨精英赛 混合果汁(juice) 【题目描述】 小R 热衷于做黑暗料理,尤其是混合果汁。 商店里有n 种果汁,编号为0, 1, 2, . . . , n −1。i 号果汁的美味度是di,每升价格为 pi。小R 在制作混合果汁时,还有一些特殊的规定,即在一瓶混合果汁中,i 号果汁最 多只能添加li 升。 现在有m 个小朋友过来找小R 要混合果汁喝,他们都希望小R 用商店里的果汁 制作成一瓶混合果汁。其中,第j 个小朋友希望他得到的混合果汁总价格不大于gj,体 积不小于L j。在上述这些限制条件下,小朋友们还希望混合果汁的美味度尽可能地高, 一瓶混合果汁的美味度等于所有参与混合的果汁的美味度的最小值。请你计算每个小 朋友能喝到的最美味的混合果汁的美味度。 【输入格式】 从文件juice.in 中读入数据。 输入第一行包含两个正整数n, m,表示果汁的种数和小朋友的数量。 接下来n 行,每行三个正整数di, pi, li,表示i 号果汁的美味度为di,每升价格为 pi,在一瓶果汁中的添加上限为li。 接下来m 行依次描述所有小朋友:每行两个数正整数gj, L j 描述一个小朋友,表 示他最多能支付gj 元钱,他想要至少L j 升果汁。 【输出格式】 输出到文件juice.out 中。 对于所有小朋友依次输出:对于每个小朋友,输出一行,包含一个整数,表示他能 喝到的最美味的混合果汁的美味度。如果无法满足他的需求,则输出−1。 【样例1 输入】 3 4 1 3 5 2 1 3 3 2 5 6 3 5 3 10 10 20 10 第2 页 共8 页 第二试混合果汁(juice) IOI 2018 中国国家队选拔赛暨精英赛 【样例1 输出】 3 2 -1 1 【样例2】 见选手目录下的juice/juice2.in 与juice/juice2.ans。 【样例3】 见选手目录下的juice/juice3.in 与juice/juice3.ans。 【子任务】 对于所有的测试数据,保证n, m ≤100000,1 ≤di, pi, li ≤105,1 ≤gj, L j ≤1018。 测试点编号 其他限制 n = m = 1-3 10 10 无 4-6 500 500 7-9 5000 5000 10-12 pi = 1 13-15 li = 1 100000 100000 无 16-20 第3 页 共8 页
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3 4
1 3 5
2 1 3
3 2 5
6 3
5 3
10 10
20 10
3
2
-1
1