学校题求调（时间超限）题目不难

#include<bits/stdc++.h>
using namespace std;
const int N=1550;
typedef long long ll;
int a[N][N],g[N][N],n,m,k,cnt;
ll ans=-1;
struct node{
	int x,y,v;
	bool operator<(const node&p)const{
		return v>p.v;
	}
}f[N*N];
bool check(int x1,int y1,int x2,int y2){
	if(y1+k<=y2||y1>=y2+k)return 1;
	else if(x1+k<=x2||x1>=x2+k)return 1;
	else return 0;
}
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[i][j],g[i][j]=g[i][j-1]+a[i][j]+g[i-1][j]-g[i-1][j-1];//g维护一个前缀和 
	for(int i=1;i<=n-k+1;i++)
		for(int j=1;j<=m-k+1;j++)
			f[++cnt].v=g[i+k-1][j+k-1]-g[i-1][j+k-1]-g[i+k-1][j-1]+g[i-1][j-1],f[cnt].x=i,f[cnt].y=j;//f存每一个k*k的值 
	sort(f+1,f+cnt+1);
	for(int i=1;i<cnt;i++){//找出两个最大的值且不重叠 ，从大到小找
		if(f[i].v+f[i+1].v<ans)break;//最大都不行就说明找完了 
		for(int j=i+1;j<=cnt;j++){
			if(f[i].v+f[j].v<ans)break; 
			if(check(f[i].x,f[i].y,f[j].x,f[j].y)&&f[i].v+f[j].v>ans){//不重叠且比已知的大，那就更新 
				//cout<<f[i].x<<" "<<f[i].y<<" "<<f[j].x<<" "<<f[j].y<<endl;
				ans=f[i].v+f[j].v;
				break;//之后的j无意义 
			}
		}
	}
	cout<<ans;
	return 0;
}