分数: 550 点
问题陈述
有苹果树排列在数轴上,并且 N 苹果从树上掉下来。
具体来说,对于每个 1\leq i\leq N,一个苹果落在坐标处 X_i 时间 T_i.
高桥有一个耐用的篮子 D 和长度 W,他可以采取以下行动 正好一次.
选择正整数 S 和 L。他架起篮子以覆盖射程 L-0.5\leq x\leq L+W-0.5 时间 S-0.5,并在时间检索它 S+D-0.5。 他得到了从篮子被放置到被取回之间落入篮子覆盖范围内的所有苹果。
篮子一旦设置好,他就不能再移动它,一旦取回篮子,他也不能再次设置它。
找出他能得到的最大苹果数。
约束
- 1 \leq N\leq 2\times 10^5
- 1 \leq D\leq 2\times 10^5
- 1 \leq W\leq 2\times 10^5
- 1 \leq T_i\leq 2\times 10^5
- 1 \leq X_i\leq 2\times 10^5
- 所有对 (T_i,X_i) 不同。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N D W T_1 X_1 T_2 X_2 \vdots T_N X_N
输出
打印高桥可以获得的最大苹果数。
示例输入 1
8 4 3 1 1 3 4 6 4 5 2 4 2 4 3 5 5 7 3
示例输出 1
5
如果高桥选择 S=3 和 L=2,他会设置篮子来覆盖范围 1.5\leq x\leq 4.5 从时间 2.5 to 6.5。然后,他得到以下五个苹果:
- 落在坐标处的苹果 X_2=4 时间 T_2=3
- 落在坐标处的苹果 X_3=4 时间 T_3=6
- 落在坐标处的苹果 X_4=2 时间 T_4=5
- 落在坐标处的苹果 X_5=2 时间 T_5=4
- 落在坐标处的苹果 X_6=3 时间 T_6=4
没有办法得到六个或更多的苹果,所以打印 5.