P2390 Visiting Landmarks

Adapted from USACO 2007 November Bronze "Exploration".

Bessie is traveling along a road with many landmarks and wants to visit as many landmarks as possible before sunset. Bessie can move one unit of distance per minute. Treat the road as a number line. Bessie starts at the origin. There are $n(1 \le n \le 5\times 10^4)$ landmarks on the road, each with a distinct coordinate $x_i(|x_i| \le 10^5)$. Sunset occurs after $t(1 \le t \le 10^9)$ minutes.

The first line: two integers $t,n$. The second line to line $n+1$: the coordinates $x_i$.

A single integer: the maximum number of landmarks Bessie can visit.

1. Bessie does not need to return to the origin at sunset. 2. This differs from the original simple simulation problem. 3. The testdata has been modified compared to the original problem. Translated by ChatGPT 5