求助!57分的代码
查看原帖
求助!57分的代码
1058017
Youuu888楼主2024/1/21 19:27

思路是先求每一列的前缀和,两层for枚举左上角的点,内层的for求c列的sum和

#include<cstdio>
using namespace std;
int N[1030][1030];
int n,m,c,x=0,y=0;
long long ans=-9999999;
int main(void){
    scanf("%d %d %d",&n,&m,&c);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int a;
            scanf("%d",&a);
            N[i][j]=N[i-1][j]+a;
        }
    }//二维前缀和
    for(int ihigh=0;ihigh<=n-c;ihigh++){
        int ilow=ihigh+c;
        for(int j=1;j<=n-c;j++){
            long long sum=0;
            for(int q=j;q<=j+c;q++){
                sum+=N[ilow][q]-N[ihigh][q];
            }
            if(sum>ans){
                ans=sum;
                x=ihigh+1;
                y=j;
            }
        }
    }
    printf("%d %d",x,y);

}
2024/1/21 19:27
加载中...