Cakes for Clones
Contest: Technocup 2021 - Elimination Round 2
Difficulty rating: 2900
Tags: dp

You live on a number line. You are initially (at time moment $$$t = 0$$$) located at point $$$x = 0$$$. There are $$$n$$$ events of the following type: at time $$$t_i$$$ a small cake appears at coordinate $$$x_i$$$. To collect this cake, you have to be at this coordinate at this point, otherwise the cake spoils immediately. No two cakes appear at the same time and no two cakes appear at the same coordinate.

You can move with the speed of $$$1$$$ length unit per one time unit. Also, at any moment you can create a clone of yourself at the same point where you are located. The clone can't move, but it will collect the cakes appearing at this position for you. The clone disappears when you create another clone. If the new clone is created at time moment $$$t$$$, the old clone can collect the cakes that appear before or at the time moment $$$t$$$, and the new clone can collect the cakes that appear at or after time moment $$$t$$$.

Can you collect all the cakes (by yourself or with the help of clones)?

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 5000$$$) — the number of cakes.

Each of the next $$$n$$$ lines contains two integers $$$t_i$$$ and $$$x_i$$$ ($$$1 \le t_i \le 10^9$$$, $$$-10^9 \le x_i \le 10^9$$$) — the time and coordinate of a cake's appearance.

All times are distinct and are given in increasing order, all the coordinates are distinct.

Output format:
Print "YES" if you can collect all cakes, otherwise print "NO".

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first example you should start moving towards $$$5$$$ right away, leaving a clone at position $$$1$$$ at time moment $$$1$$$, and collecting the cake at position $$$2$$$ at time moment $$$2$$$. At time moment $$$5$$$ you are at the position $$$5$$$ and collect a cake there, your clone collects the last cake at time moment $$$6$$$.

In the second example you have to leave a clone at position $$$0$$$ and start moving towards position $$$5$$$. At time moment $$$1$$$ the clone collects a cake. At time moment $$$2$$$ you should create a new clone at the current position $$$2$$$, it will collect the last cake in future. You will collect the second cake at position $$$5$$$.

In the third example there is no way to collect all cakes.

Example input:
3
2 2
5 5
6 1

Example output:
YES

Example input:
3
1 0
5 5
6 2

Example output:
YES

Editorial:
Let $$$mintime_i$$$ be the minimum time we can get to coordinate $$$x_i$$$ given that all previous cakes are collected and the latest created clone is already useless. Also let $$$dp_{i, j}$$$ be a boolean being true if we can reach a situation where we just collected the $$$i$$$-th cake, and our clone is currently waiting for the cake $$$j$$$ in correct position.
Let us currently be in the position of the $$$i$$$-th event and the latest clone is useless (state $$$mintime_i$$$). Then it is always optimal to collect the $$$i$$$-th cake with a new clone while we move somewhere. There are two possible options for further actions:
1. We directly go to the next event. Then we just need to update $$$mintime_{i + 1}$$$, and not forget to wait for the clone to collect the $$$i$$$-th cake.
2. We want to leave clone somewhere waiting for some $$$j$$$-th cake and go take the $$$(i + 1)$$$-th cake ourselves. Then if we have enough time to do that, make $$$dp_{i+1, j}$$$ reachable.
Let us be in the state $$$dp_{i, j}$$$ (we have just collected the $$$i$$$-th cake, and our clone is waiting for the $$$j$$$-th cake). If $$$i + 1 \neq j$$$, then we should just go and collect the $$$i + 1$$$-th cake, otherwise there are two possibilities:
1. The $$$j+1$$$-th cake is collected by a new clone, then we have to updated $$$mintime_{j+1}$$$.
2. We want to leave a new clone waiting for some later cake $$$k$$$ (after the old one collects cake $$$j$$$), and take the $$$j+1$$$-th cake ourselves, then the transition leads to the state $$$dp_{j+1, k}$$$.
We can collect all cakes if $$$mintime_n \leq t_n$$$, or $$$dp_{n - 1, n}$$$ is reachable.
The total complexity is $$$O(n^2)$$$, because we only loop through the position of the next clone in $$$O(n)$$$ states.