Ball Stacking - ICPC Latin America 2011

This time I solved the problem Ball Stacking from ICPC Latin America 2011, the statement for this problem is available here.

This problem is solved with dynamic programming. The first thing that should be done to make things easier is changing the organization of the balls, so that each ball depends on the balls to its left and above it. So, this way one ball can only be taken if all the balls from the rectangle with it and the first ball as extremes have also been taken.

Following this, each cell is initialized with the sum of all the balls that must be taken for the current ball to also be taken. Later, the maximum sum is the maximum of the total sum of the current cell plus the value of the cell on its top and to its left, which has already been processed.

The last part is to update the value of the cell. It is the maximum of: {the column going from the top till the current ball, this column plus the value to its top and right, this column plus the value to its right, the value right on top of the current ball}. The column is taken because these balls are required to take the current ball and the balls to the left have still to be processed, they shall take care of taking the balls on top of them. Then the column must be taken together with both the value to the right and to the right and top because these balls to the right require that the ones to the left also be taken. There is still the possibility of taking no extra balls and using the value of the ball above.

I know the explanation was not very good, so any questions you may ask.


My code is available at http://codepad.org/NlZWcutk