P10341 [THUSC 2019] Emergency Decision

On a coastline, there are $n$ lighthouses, numbered from $1$ to $n$. The coastline can be seen as a number line, and each lighthouse can be seen as a point on the number line. The position of lighthouse $i$ is $x_i$, and there is at most one lighthouse at each position. These $n$ lighthouses are arranged in increasing order of position, i.e. $x_i < x_{i+1}$ for $1 \le i < n$. Now there are exactly $n$ tourists waiting in a line outside the coastline to enter. Tourist $i$ will enter lighthouse $i$ to visit. For safety, every lighthouse that has a tourist on it must be *illuminated*. However, due to power limits on the coastline, at most $t$ lighthouses can be *turned on*. Each lighthouse has an illumination range of $q$. When the light of a lighthouse is turned on, all positions on the coastline whose distance to it is at most $q$ will be illuminated (that is, all points in the set $\{x \mid \lvert x-x_i \rvert \le q\}$ will be illuminated). Now, as the manager of the coastline tourism office, you need to decide which tourists are allowed to enter the coastline. This decision cannot be made casually, and it must satisfy the following requirements: - Safety first: there must exist a lighting plan such that the lighthouse of every tourist who enters the coastline is illuminated. - First-come-first-served: tourists earlier in the queue have priority. If some tourist cannot enter the coastline, then all tourists behind them cannot enter either. - Profit-oriented: sell as many tickets as possible, i.e. allow as many tourists as possible to enter the coastline. After careful calculation, you want to know how many tourists will enter the coastline in the end.

The first line contains three integers $n,t,q$, representing the number of lighthouses and the maximum number of lighthouses that can be turned on. The second line contains $n$ integers. The $i$-th integer $x_i$ represents the coordinate of lighthouse $i$.

Output one line with one integer, representing the number of tourists who finally enter the coastline.

**[Sample Explanation 1]** You can allow the first two tourists to enter the coastline, and turn on the first lighthouse. It can be proven that there is no valid plan that allows more tourists than this. **[Sample Explanation 2]** You can allow the first three tourists to enter the coastline, and turn on the second lighthouse. It can be proven that there is no valid plan that allows more tourists than this. **[Subtasks]** | Subtask ID | $n\le$ | $t \le $ | $q \le $ | Score | |:--:|:--:|:--:|:--:|:--:| | 1| $100$ | $100$ | $10^9$ | 20 | |2| $10^3$ | $10^3$ | $10^9$ | 20 | |3| $10^4$ | $10^4$ | $10^9$ | 20 | |4| $10^5$ | $10^5$ | $10^9$ | 20 | |5| $7.5\times10^6$ | $7.5\times10^6$ | $10^9$ | 20 | Translated by ChatGPT 5