写了段代码,最后一个点TLE,优化后变WA,看到讨论组说二维要开long long,结果答案完全炸掉
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,c,map[1005][1005],dp[1005][1005],h[1005][1005],ans,x,y;
int main(){
cin>>n>>m>>c;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&map[i][j]);
for(int i=1;i<=n;i++) h[i][1]=map[i][1];
for(int i=1;i<=n;i++)
for(int j=2;j<=m;j++)
h[i][j]=h[i][j-1]+map[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
dp[i][j]=dp[i-1][j]+h[i][j];
for(int i=n;i>=1;i--)
for(int j=m;j>=1;j--){
dp[i][j]-=dp[i-c][j];
dp[i][j]-=dp[i][j-c];
dp[i][j]+=dp[i-c][j-c];
}
for(int i=c;i<=n;i++)
for(int j=c;j<=m;j++){
if(ans<dp[i][j]){
x=i;
y=j;
ans=dp[i][j];
}
}
printf("%d %d",x-c+1,y-c+1);
return 0;
}