#P17544. [JAG 2026 Summer Camp #2] Two Greedy Customers
[JAG 2026 Summer Camp #2] Two Greedy Customers
题目描述
一家商店出售 种商品,编号为 到 。第 种商品的价格为 。
两位顾客 Alice 和 Bob 将分别来到商店。Alice 购买第 种商品可以获得 的满意度,Bob 购买它则可以获得 的满意度。初始时,Alice 有 单位的钱,Bob 有 单位的钱。
在他们到来之前,作为店员的你要为这 种商品确定一个排列顺序。每位顾客都会独立地按照这个顺序逐一考虑各类商品,并遵循以下规则购物。
- 顾客从左到右逐一查看商品。
- 如果当前商品的价格不大于顾客此时拥有的钱数,顾客就一定会购买一件该商品,并支付相应价格。
- 否则,顾客不购买该商品。
每种商品的库存都足够充足,Alice 和 Bob 的购买行为互不影响。
每位顾客的得分为其购买的所有商品带来的满意度之和。通过恰当地排列商品,求 Alice 和 Bob 的得分之和的最大可能值。
输入格式
输入仅包含一组测试数据,格式如下。
N A B
C_1 U_1 V_1
C_2 U_2 V_2
...
C_N U_N V_N
整数 为商品种类数()。整数 分别为 Alice 和 Bob 初始拥有的钱数()。
对于每个 ,整数 为第 种商品的价格()。整数 分别为 Alice 和 Bob 购买第 种商品时获得的满意度()。
输出格式
在一行中输出 Alice 和 Bob 的得分之和的最大可能值。
2 6 8
3 10 1
5 8 10
21
2 1 1
1 5 1
1 1 10
11
3 5 6
4 1 100
3 100 1
2 10 10
220
提示
在第一个样例中,若将商品按 的顺序排列,Alice 只购买第 种商品,得分为 ;Bob 购买两种商品,得分为 。总得分为 ,这就是最大可能值。