灰灰的飞机

灰灰的飞机

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

历史记录

10.14 本题数据已加强
10.19 感谢whx大佬指正(伪)std的错误。用新的(伪)std重新生成了数据
11.04 感谢whx大佬指出\(h\)范围的错误,更新了题面和数据,得到了真正的std!!!(感谢whx大佬)
11.04 同步题目 洛谷U379082 灰灰的飞机
11.05 使用树状数组std跑的数据有误(std写错啦啊哈哈哈哈)重新生成了数据...

题目描述

题目背景

据说灰灰小时候曾指着天上的飞机,说:“我要把这个飞机打下来!”(Meweing跟我说的)

题目内容

灰灰为了实现小时候的梦想,研发了一款打飞机系统。
我们给天上的\(N\)架飞机从\(1\)~\(N\)编号,第\(i\)架飞机有一个高度\(h_i\)和一个打击成本\(w_i\)
但是这套系统有很大的局限性,他只能攻击\(N\)架飞机中的一个严格上升序列中的飞机;并且打飞机的打击总成本要在区间\([0, W]\)内。
现在告诉你所有数据,灰灰想知道他最多能打多少架飞机。

输入格式

第一行两个整数\(N, W\)
接下来的\(N\)行,每行两个整数\(h_i, w_i\)

输出格式

一个整数,最多能打几架飞机

样例

输入

6 5
1 1
2 1
4 1
1 1
3 1
4 1

输出

4

数据规模

对于\(20\%\)的数据,\(1 \leqslant N, W \leqslant 1000\)
对于\(60\%\)的数据,\(1 \leqslant N, W \leqslant 1500\)
对于\(100\%\)的数据,\(1 \leqslant N, W \leqslant 3000, h \leqslant 10000\)

奖励

AC奖励王老师的贴贴一个!!!

AKIOI Round #1

未参加
状态
已结束
规则
OI
题目
4
开始于
2024-08-08 08:30
结束于
2024-08-08 12:30
持续时间
4.0 小时
主持人
参赛人数
2