ZOJ Problem Set - 3222
Consider the following situation. Each grid point in an infinite two-dimention plane is assigned an integer value. All values except a very special group of points lying in a matrix of N * M are ZERO. The values in the matrix will be given.
Now you have a board of rectangle of size H * W. Cut the board into two rectangles. Assume that their sizes are a1 * b1 and a2 * b2 (These four numbers should all be positive integers). We can use them to cover a matrix of a1 * b1 and a matrix of a2 * b2. You are to maximize the sum of all the values in the two matrices.
Note: The board CANNOT rotate but the two matrices can overlap(Values in both matrices are counted twice).
There are no more than 30 cases. Proceed till the end of file.
For each case print the max sum.
3 4 3 2 -1 1 -1 -1 -1 1 -1 -1 -1 1 -1 -1
Author: ZHUANG, Junyuan
Source: ZOJ Monthly, July 2009