Binary Searching on a D&C DP Problem

Problems and Contests
#1

Can someone explain how to binary search on a D&C DP problem?

Like Submission #87726035 - Codeforces? As far as I can tell, the time complexity here (after precalculating the costs) is \mathcal O(N\cdot \log N\cdot \log \text{max value}) which is a lot more efficient than the \mathcal O(N\cdot K\cdot \log N) D&C DP.

Thanks in advance!

#2

didn’t look carefully but appears to be

1 Like
#3

Thanks!