← 返回题目列表

Codeforces · 1415/F

F. 克隆蛋糕

中文机器翻译题面 查看原题

你生活在数轴上。您最初(在时刻 $$$t = 0$$$)位于点 $$$x = 0$$$。存在以下类型的 $$$n$$$ 事件:在时间 $$$t_i$$$ 坐标 $$$x_i$$$ 处出现一个小蛋糕。要收集这个蛋糕,你此时必须处于这个坐标,否则蛋糕会立即变质。没有两个蛋糕同时出现,也没有两个蛋糕出现在同一坐标处。

每1个时间单位你可以以$$$1$$$长度单位的速度移动。此外,您可以随时在您所在的同一位置创建您自己的克隆。分身无法移动,但它会为你收集出现在该位置的蛋糕。当您创建另一个克隆时,该克隆就会消失。如果新克隆是在$$$t$$$时刻创建的,则旧克隆可以收集在$$$t$$$时刻之前或之后出现的蛋糕,而新克隆可以收集在$$$t$$$时刻或之后出现的蛋糕。

你能收集到所有蛋糕吗(自己或者在克隆人的帮助下)?

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5000$$$) — 蛋糕的数量。

接下来的 $$$n$$$ 行包含两个整数 $$$t_i$$$ 和 $$$x_i$$$ ($$$1 \le t_i \le 10^9$$$, $$$-10^9 \le x_i \le 10^9$$$) - 蛋糕出现的时间和坐标。

所有时间都是不同的,并且按升序给出,所有坐标都是不同的。

输出

如果你能收集到所有蛋糕,则打印“YES”,否则打印“NO”。

示例

输入 #1

3
2 2
5 5
6 1

输出 #1

YES

输入 #2

3
1 0
5 5
6 2

输出 #2

YES

输入 #3

3
2 1
5 5
6 0

输出 #3

NO

注意

在第一个示例中,您应该立即开始向 $$$5$$$ 移动,在 $$$1$$$ 时刻将克隆留在位置 $$$1$$$,并在 $$$2$$$ 时刻在位置 $$$2$$$ 收集蛋糕。在 $$$5$$$ 时刻,您位于 $$$5$$$ 位置并在那里收集了一个蛋糕,您的克隆体在 $$$6$$$ 时刻收集了最后一个蛋糕。

在第二个示例中,您必须将克隆留在位置 $$$0$$$ 并开始向位置 $$$5$$$ 移动。在 $$$1$$$ 时刻,克隆人收集了一个蛋糕。在$$$2$$$时刻,你应该在当前位置$$$2$$$创建一个新的克隆,它将在将来收集最后一个蛋糕。您将在 $$$5$$$ 位置领取第二块蛋糕。

在第三个示例中,无法收集所有蛋糕。