This is a classic RMQ problem. For every cow, we maintain a running maximum of the number of crosswalks that can be drawn, using the cows from
0 to j. Note that only
8 * N updates ever occur because every cow has a maximum of 8 other cows they can draw a crosswalk to.
My solution can be found here
Written by Robert Chen
Notice any mistakes? Please email us at [email protected] so that we can fix any inaccuracies.