4475: The Coolest Sub-matrix 

Time Limit(Common/Java):4000MS/12000MS     Memory Limit:65536KByte

Total Submit: 50            Accepted:13

Description

 

Given an N*N matrix, find the coolest square sub-matrix.

We define the cool value of the square matrix as X-Y where X indicating the sum of all integers of the main diagonal and Y indicating the sum of the other diagonal.

 

Input

 

The first line has a positive integer N (2 ≤ N ≤ 400), the size of the matrix.

The following N lines each contain N integers in the range [-1000, 1000], the elements of the matrix.

 

Output

 

Output the coolest value of a square sub-matrix.

 

Sample Input

2

1 -2

4 5

Sample Output

 4

Source

就是三重循环啊，大家怎么都不做，记得当时是我想错这个题了，导致当时我们队没有过这个题

就是让你随意在这个矩形选一个正方形矩阵，计算主对角线和副对角线的差值的最大值

只能枚举了，前缀和处理下，这个题只需要注意下标不一溢出就行了，思路还是很简单的，第i行j列结尾的k*k矩阵

 

#include 
       
        #include 
        
         using namespace std;int a[405][405],b[405][405];int main(){    int n;    scanf("%d",&n);    for(int i=1;i<=n;i++)    for(int j=1;j<=n;j++){        int x;        scanf("%d",&x);        a[i][j]=x+a[i-1][j-1];b[i][j]=x+b[i-1][j+1];    }    int ma=0;    for(int i=2;i<=n;i++)    for(int j=2;j<=n;j++)    for(int k=2;k<=i&&k<=j;k++)    ma=max(ma,a[i][j]-a[i-k][j-k]-b[i][j-k+1]+b[i-k][j+1]);    printf("%d\n",ma);    return 0;}