记录编号	607112	评测结果	AAAAA
题目名称	3971.不重叠正方形	最终得分	100
用户昵称	淮淮清子	是否通过	通过
代码语言	C++	运行时间	0.699 s
提交时间	2025-10-05 17:06:30	内存使用	34.14 MiB

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 1e3 + 5;

int n, m, a[MAXN][MAXN], pre[MAXN][MAXN], sum[MAXN][MAXN];
int tl[MAXN][MAXN], tr[MAXN][MAXN];
int bl[MAXN][MAXN], br[MAXN][MAXN];

signed main() {
    ios::sync_with_stdio(0);
    cin.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]});
        }
    }
    int 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;
    return 0;
}