Score : $550$ points

问题描述

在数轴上排列着苹果树，共有 $N$ 个苹果从树上落下。具体来说，对于每个 $1\leq i\leq N$，第 $i$ 个苹果在时刻 $T_i$ 落在坐标点 $X_i$。

高桥有一个篮子，其耐久度为 $D$，长度为 $W$，他可以精确地执行一次以下操作：

选择正整数 $S$ 和 $L$。他在时刻 $S-0.5$ 将篮子设置在范围 $L-0.5\leq x\leq L+W-0.5$ 内，并在时刻 $S+D-0.5$ 收回篮子。在这段时间内，篮子覆盖范围内落下的所有苹果都会被他收集到。

一旦篮子被设置好后就不能移动，而且一旦收回篮子后就不能再次设置。
请找出高桥最多可以获得的苹果数量。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There are apple trees lined up on a number line, and $N$ apples fall from the trees.
Specifically, for each $1\leq i\leq N$, an apple falls at coordinate $X_i$ at time $T_i$.

Takahashi has a basket with durability $D$ and length $W$, and he can take the following action exactly once.

Choose positive integers $S$ and $L$. He sets up the basket to cover the range $L-0.5\leq x\leq L+W-0.5$ at time $S-0.5$, and retrieves it at time $S+D-0.5$. He gets all the apples that fell into the range covered by the basket between the time it was set up and the time it was retrieved.

He cannot move the basket once it has been set up, nor can he set it up again once it has been retrieved.
Find the maximum number of apples that he can get.

Constraints

• $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$
• All pairs $(T_i,X_i)$ are different.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $D$ $W$

$T_1$ $X_1$

$T_2$ $X_2$

$\vdots$

$T_N$ $X_N$

Output

Print the maximum number of apples that Takahashi can get.

Sample Input 1

8 4 3
1 1
3 4
6 4
5 2
4 2
4 3
5 5
7 3

Sample Output 1

5

If Takahashi chooses $S=3$ and $L=2$, he will set up the basket to cover the range $1.5\leq x\leq 4.5$ from time $2.5$ to $6.5$. Then, he gets the following five apples:

• The apple that falls at coordinate $X_2=4$ at time $T_2=3$
• The apple that falls at coordinate $X_3=4$ at time $T_3=6$
• The apple that falls at coordinate $X_4=2$ at time $T_4=5$
• The apple that falls at coordinate $X_5=2$ at time $T_5=4$
• The apple that falls at coordinate $X_6=3$ at time $T_6=4$

There is no way to get six or more apples, so print $5$.

update @ 2024/3/10 01:51:45