题解 P2213 【[USACO14MAR]The Lazy Cow S】

暴力对于每一行做前缀和，枚举中间点即可
时间复杂度$O(n^3)$，可以通过S组的此题

#include<iostream>
#define int long long
using namespace std;
int a[405][405];
int sum[405][405];
signed main(){
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
			sum[i][j]=sum[i][j-1]+a[i][j];
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			int s=0;
			for(int l=max(i-k,0ll);l<=i;l++){
				s+=sum[l][min(j+l+k-i,n)]-sum[l][max(j-l-k+i-1,0ll)];
			}
			for(int l=i+1;l<=min(i+k,n);l++){
				s+=sum[l][min(j+i-l+k,n)]-sum[l][max(j-i-k+l-1,0ll)];
			}
			ans=max(ans,s); 
		}
	}
	cout<<ans;
	return 0;
}