It is ready: link
What a nice problem. Of course misof was the problem setter. It would have been obvious if you solved the contest before the Problem Writer guessing contest. This is not the first twist on binary search that misof pulled.
I still think the top-level idea of my initial idea during the match was sort of correct, dynamic programming + ternary search, but there is no viable way to make it run in time.