MINES4 - Four Mines
A Company that Makes Everything (ACME) has entered the surface mining business. They bought a rectangular field which is split into cells, with each cell having a profit value. A mine is a non-empty rectangular region, and the profit of a mine is equal to the sum of the values of all its cells. ACME wants to extract ore from four different non-overlapping mines. You are to choose these mines to maximize the total profit.
The first line contains an integer T (1 ≤ T ≤ 5), denoting the number of test cases.
For each test case, the first line contains two positive integers R and C (2 ≤ R,C ≤ 100), denoting the number of rows and columns of a rectangular field.
Each of next R lines contain C integers between -10000 and 10000, denoting a profit value for each cell in that row.
For each test case, print a number on its own line, denoting the maximum total profit that can be extracted from four mines.
Input: 2 5 5 10 10 -1 -1 10 10 -1 -1 -1 10 -1 -1 -1 -1 -1 -1 -1 -1 10 10 10 -1 -1 10 10 2 3 -1 -2 -3 -4 -5 66 Output: 99 60
n^4 is not too slow for the problem.
You must take into account that SPOJ is relatively slow. You may want to test the speed on the site itself. Find a problem with a very big time limit (for example XC) hardcode the input data into code and ignore input stream. Then see how much time it will take to execute and give WA for example. There is also and Ideone.com system, running on the same engine, but that seems to be much faster than SPOJ.
Can you check submission ID 5313130