P5119 [USACO18DEC] Convention S

A unique cow grass-eating convention is about to be held at Farmer John’s farm. Cows from all over the world will arrive at the local airport to attend the convention and eat grass. Specifically, there are $N$ cows arriving at the airport ($1\le N\le 10^5$), and cow $i$ arrives at time $t_i$ ($0\le t_i\le 10^9$). Farmer John has arranged $M$ buses ($1\le M\le 10^5$) to pick up these cows at the airport. Each bus can carry $C$ cows ($1\le C\le N$). Farmer John is waiting at the airport and plans to assign arriving cows to buses. When the last cow assigned to a bus arrives, that bus can depart. Farmer John wants to be a good host, so he does not want the cows to wait at the airport for too long. If Farmer John schedules the buses optimally, what is the minimum possible value of the maximum waiting time among all cows? A cow’s waiting time is the difference between her arrival time and the departure time of the bus she takes. The input guarantees that $MC\ge N$.

The first line contains three space-separated integers $N$, $M$, and $C$. The second line contains $N$ space-separated integers, representing the arrival time of each cow.

Output one line containing the minimum possible value of the maximum waiting time among all arriving cows.

If two cows arriving at time $1$ take the first bus, the cows arriving at times $3$ and $4$ take the second bus, and the cows arriving at times $10$ and $14$ take the third bus, then the cow with the longest waiting time waits for $4$ units of time (the cow arriving at time $10$ waits from time $10$ until time $14$). Translated by ChatGPT 5