P6174 [USACO16JAN] Angry Cows S

Bessie designed a new game: *Angry Cows*. In this game, the player launches cows, and each cow explodes on landing, detonating hay bales within a certain range. The goal of the game is to use a set of cows to detonate all the hay bales. There are $N$ hay bales located at distinct positions on a number line. The position of the $i$-th hay bale is $x_i$. If a cow with power $R$ lands at position $x$, she will detonate all hay bales in the range $[x-R, x+R]$. You can now launch $K$ cows, each with power $R$. You need to determine the minimum value of $R$ such that all hay bales can be detonated using $K$ cows.

The first line contains two integers $N, K$ ($1 \leq N \leq 5 \times 10^4$, $1 \leq K \leq 10$). The next $N$ lines each contain an integer $x_i$ ($0 \leq x_i \leq 10^9$).

Output one integer, the minimum value of $R$.

Translated by ChatGPT 5