# USACO Gold Painting the Barn

http://www.usaco.org/index.php?page=viewproblem2&cpid=923

The sample test case doesn’t seem to make sense (It does, I just can’t see it)

This is the array that shows the coats of paint for each cell.
1 1 1 0 0 0
1 2 2 1 1 1
1 2 3 2 2 1
0 1 2 2 2 1
0 1 2 2 2 1
0 1 2 2 2 1
0 1 1 1 1 1

This is the conversion to a 1 -1 array.
1 1 1 0 0 0
1 -1 -1 1 1 1
1 -1 0 -1 -1 1
0 1 -1 -1 -1 1
0 1 -1 -1 -1 1
0 1 -1 -1 -1 1
0 1 1 1 1 1

The ideal solution seems to be to keep all the -1’s, which adds up to 14. Then paint the right most column 2 left most columns, which adds up to 10. However, this only adds up to 24 while the answer is 26.

The only thing I can really think of is that the two -1’s I covered painting the left side didn’t count? (Sorry if that doesn’t make sense)

Is there a more ideal solution or am I misunderstanding? Any help would be greatly appreciated

The points given aren’t cells, but coordinates.

I don’t think that’s the issue. I was always using the coordinates as corners.

I don’t think so because the box around (1,1)\rightarrow (4,4) should be a 3\times 3 square.