I’m still not sure if your algorithm is correct for this version of the problem. We can only drop cows where haybales are, and what your algorithm does is drop a cow so that it just reaches the leftmost unexploded bale.

I did not see such requirement, and it passed the USACO online judge.

we’re talking about a modified version of the problem here…

I have a O(n\lg^2 n) solution with your adjusted problem.

First do binary search, then do dynamic programming.

let \text{dp}[i] be the minimal amount of cows needed to make 1-i covered.

then we binary search l and r, which is the first element of x[] out of the [x[i]-mid,x[i]+mid].

Then \text{dp}[k] = min(\text{dp}[k],\text{dp}[l]+1) \text{ where [l<k<r]}

This can be optimized into O(n \lg n) using segment tree. Considering the binary search that we did initially, the time complexity is O(n\lg^2 n)

The dp is a range minimum where the left endpoint moves monotonically right, which can be done in O(N) time with a deque.

But you can notice that you don’t even need a range minimum, since the dp table is monotonically increasing (if you define it to be dp[i] = covering at least cows 1 through i). So it can be done with two pointers in O(n), more or less equivalent to the greedy solution.