P1719 最大加权矩形

zhonghangkuan123 · 2025-10-06 15:34:59 · 算法·理论

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
long long a[N][N],b,c,xx,yy,cnt,d,e,f,g,mmax=-1e4,t,sum=0,n,m,s[N][N],x,y;

int main(){ 
   cin>>n;
   for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
          }
    }
   for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=i;k++){
                for(int t=1;t<=j;t++){
                    mmax=max(mmax,s[i][j]-s[k-1][j]-s[i][t-1]+s[k-1][t-1]); 
                }
            }
       }
   }
   cout<<mmax;
   return 0;

}

代码