i was trying to solve this problem but got wrong answer on some test cases
http://www.usaco.org/index.php?page=viewproblem2&cpid=923
My approach was. i stored the maximum paint can be done from the current point to left corners and right corners and then iterate over whole grid and find max possible point from where i can paint 2 rectanges which will give me max answer
here is my submission