Problem: dp2
You're a land speculator considering buying a region of land. The land you're looking at is divided into square blocks; you've had each block assessed so you know its value. You can buy as much land as you want, but only in one rectangular region. Here's the problem: some of the land is so useless, it's not worth the money it would cost you to buy it! Your goal, then, should be to pick one rectangle of land that maximizes your profit.
Input
The input is a single test case. First is an integer n, the dimensions of the land area (it will be square). Next come n2 integers, the values of the individual squares of land.
Bounds
Your code will be run 40 times on 40 distinct test cases. In each test case, 1 ≤ n ≤ 100, and the value of each parcel of land will be between −127 and 127.
Output
Output a single integer, the maximum achievable value, followed by a newline. Note that you must buy at least one parcel of land (i.e. you cannot choose the empty set).
Sample Input
6 49 36 -94 99 -117 -100 35 61 -76 81 -116 90 81 -91 -65 -14 78 15 -40 -18 -47 124 103 73 -59 -38 31 -21 -118 -119 -6 -69 -84 -101 -98 53
Sample Output
434