Advertisement
Guest User

10827

a guest
Jul 5th, 2015
192
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.29 KB | None | 0 0
  1. #include <cstdio>
  2. #define rep(i, a, n) for(int i = a; i < (n); i++)
  3. #define max_int(a, b) (a > b? a : b)
  4.  
  5. using namespace std;
  6. int grid[155][155];
  7.  
  8. int main()
  9. {
  10.     int N, temp_sum, max_sum, T, range;
  11.     scanf("%d", &T);
  12.     while(T--)
  13.     {
  14.         max_sum = -2250000;
  15.         scanf("%d", &N);
  16.  
  17.         rep(i, 0, N) rep(j, 0 ,N )
  18.         {
  19.             scanf("\n %d", &grid[i][j]);
  20.             grid[i+N][j] = grid[i][j];
  21.             grid[i][j+N] = grid[i][j];
  22.             grid[i+N][j+N] = grid[i][j];
  23.         }
  24.  
  25.         range = N;
  26.         N *= 2;
  27.  
  28.         rep(i, 0, N) rep(j, 0, N)
  29.         {
  30.             if(i > 0) grid[i][j] += grid[i-1][j]; //up
  31.             if(j > 0) grid[i][j] += grid[i][j-1]; // left
  32.             if(i > 0 && j > 0) grid[i][j] -= grid[i-1][j-1]; //inclusion- exclusion
  33.         }
  34.  
  35.         //(i,j) -> top left coordinate, (k, l) -> bottom right coordinate
  36.         rep(i, 0, range) rep(j, 0,  range) rep(k, i, i + range) rep(l, j, j + range)
  37.         {
  38.             temp_sum = grid[k][l];
  39.             if(i > 0) temp_sum -=  grid[i-1][l];
  40.             if(j > 0) temp_sum -= grid[k][j-1];
  41.             if(i > 0 && j > 0) temp_sum += grid[i-1][j-1];
  42.             max_sum = max_int(temp_sum, max_sum);
  43.         }
  44.  
  45.         printf("%d\n", max_sum);
  46.     }
  47.     return 0;
  48. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement