记录编号	588148	评测结果	AAAAA
题目名称	不重叠正方形	最终得分	100
用户昵称	zxhhh	是否通过	通过
代码语言	C++	运行时间	1.878 s
提交时间	2024-05-27 18:49:44	内存使用	40.45 MiB

#include <bits/stdc++.h>

using namespace std;
const int N = 1005; 
typedef long long ll; 
int n, m, a[N][N]; 
ll s[N][N], v[N][N], f[N][4], ans, g[N][N][2], p[N]; 

void solve (int op) {
    memset(f, -0x3f, sizeof f); memset(g, -0x3f, sizeof g); memset(p, -0x3f, sizeof p); 
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            s[i][j] = s[i-1][j]+s[i][j-1]-s[i-1][j-1]; 
            if (op == 0) s[i][j] += a[i][j]; 
            if (op == 1) s[i][j] += a[n-i+1][n-j+1]; 
            if (op == 2) s[i][j] += a[n-i+1][j]; 
            if (op == 3) s[i][j] += a[i][n-j+1]; 
            if (op == 4) s[i][j] += a[j][i]; 
            if (op == 5) s[i][j] += a[n-j+1][n-i+1]; 
            if (op == 6) s[i][j] += a[n-j+1][i]; 
            if (op == 7) s[i][j] += a[j][n-i+1]; 
            if (i >= m && j >= m) v[i][j] = s[i][j]-s[i-m][j]-s[i][j-m]+s[i-m][j-m]; 
            else v[i][j] = -1e18; 
        }
    }
    for (int i = n;i >= 1;i--) {
        for (int j = 1;j <= n;j++) {
            g[i][j][0] = max({v[i][j], g[i+1][j][0], g[i][j-1][0]}); 
        }
        for (int j = n;j >= 1;j--) {
            g[i][j][1] = max({v[i][j], g[i+1][j][1], g[i][j+1][1]}); 
        }
    } 
    for (int i = 1;i <= n;i++) f[i][0] = 0; 
    for (int i = m;i <= n;i++) {
        ll k = 0; 
        for (int j = m;j <= n;j++) {
            k = max(k, v[i][j]);
        }
        for (int j = 1;j <= 3;j++) f[i][j] = max(f[i-1][j], f[i-m][j-1]+k); 
    }   
    ans = max(ans, f[n][3]); 
    for (int i = m;i <= n;i++) {
        p[i] = p[i-1]; 
        for (int j = m;j <= n;j++) {
            p[i] = max(p[i], v[i][j]); 
        }
        for (int j = m;j <= n;j++) {
            ll k = v[i][j]+p[i-m]+max(g[i][j-m][0], j+m <= n ? g[i][j+m][1] : -0x3f3f3f3f3f3f3f3f);
            ans = max(ans, k);  
        }
    }
}

int main () {
    freopen("zfx.in", "r", stdin); 
    freopen("zfx.out", "w", stdout); 
    cin >> n >> m; 
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            cin >> a[i][j]; 
        }
    }
    for (int i = 0;i < 8;i++) solve(i); 
    cout << ans; 
    return 0; 
}
/*
4 1
1 1 9 1
1 1 9 1
1 1 9 1
1 1 1 1
*/