记录编号	607089	评测结果	AAAAA
题目名称	3971.不重叠正方形	最终得分	100
用户昵称	对立猫猫对立	是否通过	通过
代码语言	C++	运行时间	0.683 s
提交时间	2025-10-05 15:44:07	内存使用	31.08 MiB

#include <bits/stdc++.h>
#define maxn 1005
using namespace std;
using ll = long long;
int n, m, a[maxn][maxn];
ll pre[maxn][maxn], sum[maxn][maxn];
ll tl[maxn][maxn], tr[maxn][maxn], bl[maxn][maxn], br[maxn][maxn];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> a[i][j];
	for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) pre[i][j] = pre[i - 1][j] + pre[i][j - 1] + a[i][j] - pre[i - 1][j - 1];
	for (int i = m; i <= n; i++) for (int j = m; j <= n; j++) sum[i][j] = pre[i][j] - pre[i - m][j] - pre[i][j - m] + pre[i - m][j - m];
	for (int i = m; i <= n; i++) for (int j = m; j <= n; j++) tl[i][j] = max({tl[i][j - 1], tl[i - 1][j], sum[i][j]});
	for (int i = m; i <= n; i++) for (int j = n - m + 1; j >= 1; j--) tr[i][j] = max({tr[i][j + 1], tr[i - 1][j], sum[i][j + m - 1]});
	for (int i = n - m + 1; i >= 1; i--) for (int j = m; j <= n; j++) bl[i][j] = max({bl[i + 1][j], bl[i][j - 1], sum[i + m - 1][j]});
	for (int i = n - m + 1; i >= 1; i--) for (int j = n - m + 1; j >= 1; j--) br[i][j] = max({br[i + 1][j], br[i][j + 1], sum[i + m - 1][j + m - 1]});
	ll ans = 0;
	for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) {
			if (i - m >= m && i + m <= n && j >= m)
				ans = max(ans, sum[i][j] + tr[i - m][1] + br[i + 1][1]);
			if (i >= m && j - m >= m && j + m - 1 <= n)
				ans = max(ans, sum[i][j] + bl[1][j - m] + br[1][j + 1]);
			if (i - 1 >= m  &&  i + m - 1 <= n  &&  j - 1 >= m && j + m - 1 <= n) {
				ans = max(ans, br[i][j] + bl[i][j - 1] + tr[i - 1][1]);
				ans = max(ans, br[i][1] + tl[i - 1][j - 1] + tr[i - 1][j]);
				ans = max(ans, br[1][j] + tl[i - 1][j - 1] + bl[i][j - 1]);
				ans = max(ans, br[i][j] + bl[1][j - 1] + tr[i - 1][j]);
			}
		}
	cout << ans << '\n';
	return 0;
}