Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #define rep(i, a, n) for(int i = a; i < (n); i++)
- #define max_int(a, b) (a > b? a : b)
- using namespace std;
- int grid[155][155];
- int main()
- {
- int N, temp_sum, max_sum, T, range;
- scanf("%d", &T);
- while(T--)
- {
- max_sum = -2250000;
- scanf("%d", &N);
- rep(i, 0, N) rep(j, 0 ,N )
- {
- scanf("\n %d", &grid[i][j]);
- grid[i+N][j] = grid[i][j];
- grid[i][j+N] = grid[i][j];
- grid[i+N][j+N] = grid[i][j];
- }
- range = N;
- N *= 2;
- rep(i, 0, N) rep(j, 0, N)
- {
- if(i > 0) grid[i][j] += grid[i-1][j]; //up
- if(j > 0) grid[i][j] += grid[i][j-1]; // left
- if(i > 0 && j > 0) grid[i][j] -= grid[i-1][j-1]; //inclusion- exclusion
- }
- //(i,j) -> top left coordinate, (k, l) -> bottom right coordinate
- rep(i, 0, range) rep(j, 0, range) rep(k, i, i + range) rep(l, j, j + range)
- {
- temp_sum = grid[k][l];
- if(i > 0) temp_sum -= grid[i-1][l];
- if(j > 0) temp_sum -= grid[k][j-1];
- if(i > 0 && j > 0) temp_sum += grid[i-1][j-1];
- max_sum = max_int(temp_sum, max_sum);
- }
- printf("%d\n", max_sum);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement