USACO February 2018 Platinum - At Large

Although the intended solution is extremely difficult, this is not too hard to fakesolve! First write some $O(N^2)$ DP that is somehow fast enough to pass test cases 1-6.

This won't work for test cases 7-11, but these test cases are quite special!

For a legit (?) DP solution, see Eric Zhang's comment.