P2855 [USACO06DEC] River Hopscotch S

Every year the cows hold a peculiar hopscotch event, carefully jumping from one rock to another in a river. The competition is on a long straight river with a rock at the start and another rock at the end, which is $L$ units away from the start ($1 \le L\le 1,000,000,000$). Between the start and end rocks, there are $N$ additional rocks ($0\le N\le 50,000 $), each at an integer distance $D_i$ from the start ($0

The first line contains three space-separated integers: $L$, $N$, and $M$. Lines $2 \dots N+1$ each contain one integer, the distance of a rock from the start. No two rocks share the same position.

Output a single integer, the maximum possible value of the minimal jump distance after removing at most $M$ rocks.

Before removing any rock, the shortest jump is a length-$2$ jump from $0$ (start) to $2$; after removing the rocks at $2$ and $14$, the required shortest jump is $4$ (from $17$ to $21$ or from $21$ to $25$). Translated by ChatGPT 5