Thing is, it doesn’t matter if you use >b ultra balls and removed the penalty for exactly b ultra balls it is still correct.
Ok let us define it the problem better. We are binary searching for C = f(b) - f(b-1), where f(x) is the optimal answer for x ultra balls.
Now, we know f(x+1) - f(x) \le f(x) - f(x-1).
Next let us define l and r.
l is the smallest value such that f(l) -f(l-1) \approx f(b) - f(b-1).
r is the largest value such that f(r) - f(r-1) \approx f(b) - f(b-1).
We know l \le b \le r.
So when we choose some C < f(b) - f(b-1), we will get optimal number of ultra balls <l, and so we will increase C, and vice versa.
So we know that C \approx f(b) - f(b-1) at the end. Now, because they are almost equal, we may get the optimal number of ultra balls, l \le U \le r.
Remember, that we are storing max(f(k) - kC). Recall that for all i,i+1, such that l \le i \le r, and l \le i+1 \le r, f(i+1) - f(i) \approx C.
That means f(i+1) - C = f(i), and f(i+1) - (i+1)C = f(i) - iC.
So it doesn’t matter what value U has between l and r. F(U) - UC = f(b) - bC, so F(U) - UC + bC = f(b).
Try this. Remember, you are calculating the maximum value and when it happens, and you are trying to change C so that the maximum is at b.