AT_abc364_e.[ABC364E] Maximum Glutton
提高+/省选-
通过率:0%
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
高桥君为すぬけ君做了 N 道菜。每道菜从 1 到 N 编号,第 i 道菜的甜度为 Ai,咸度为 Bi。
高桥君可以将这些菜按照任意顺序排列。すぬけ君会按照排列好的顺序依次吃菜,但在某一时刻,如果他已经吃过的菜的甜度总和超过 X 或咸度总和超过 Y,那么之后的菜他就不会再吃了。
高桥君希望すぬけ君能尽可能多地吃到菜。请你求出高桥君合理安排菜品顺序时,すぬけ君最多能吃到多少道菜。
输入格式
输入以以下格式从标准输入给出。
N X Y
A1 B1
A2 B2
⋮
AN BN
输出格式
请输出一个整数,表示すぬけ君最多能吃到的菜的数量。
输入输出样例
输入#1
4 8 4 1 5 3 2 4 1 5 3
输出#1
3
输入#2
2 1 1 3 2 3 2
输出#2
1
输入#3
2 100 100 3 2 3 2
输出#3
2
输入#4
6 364 463 230 381 154 200 328 407 339 94 193 10 115 309
输出#4
3
说明/提示
限制条件
- 1≤N≤80
- 1≤Ai,Bi≤10000
- 1≤X,Y≤10000
- 所有输入均为整数
样例解释 1
假设高桥君将菜按照 2,3,1,4 的顺序排列,すぬけ君的行为如下:
- 首先吃第 2 道菜。此时已吃菜的甜度总和为 3,咸度总和为 2。
- 接着吃第 3 道菜。此时已吃菜的甜度总和为 7,咸度总和为 3。
- 然后吃第 1 道菜。此时已吃菜的甜度总和为 8,咸度总和为 8。
- 由于咸度总和超过了 Y=4,之后的菜就不会再吃了。
因此,这种排列下すぬけ君最多能吃到 3 道菜。不论高桥君如何排列,すぬけ君都不可能吃到全部 4 道菜,所以答案是 3。
输入解题思路,AI测评打分。不知道怎么写?