蒟蒻求助 最后一个点怎么也过不去
  • 板块P2004 领地选择
  • 楼主向晚
  • 当前回复5
  • 已保存回复5
  • 发布时间2021/1/21 20:38
  • 上次更新2023/11/5 04:35:06
查看原帖
蒟蒻求助 最后一个点怎么也过不去
170410
向晚楼主2021/1/21 20:38

写了段代码,最后一个点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;
}
2021/1/21 20:38
加载中...