记录编号	588511	评测结果	AAAAA
题目名称	不重叠正方形	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.292 s
提交时间	2024-06-03 20:16:22	内存使用	41.94 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define F(i,a,b) for(ll i = a;i <= b;i++)
#define D(i,a,b) for(ll i = a;i >= b;i--)
#define fi first
#define se second
#define pii pair<int,int>
#define pb(x) push_back(x)
const int N = 1e3+10,M = 2e6+10;
const ll inf = 1e17,mod = 998244353;

ll read(){
    ll x = 0,f = 1;char c = getchar();
    for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
    for(;c >= '0' && c <= '9';c = getchar())x = (x<<3) + (x<<1) + c-'0';
    return x * f;
}

int n,m,k;
ll f[4][N][N],a[N][N],c[N][N],ans;
int main(){
    freopen("zfx.in","r",stdin);
    freopen("zfx.out","w",stdout);
    n = read(),k = read();
    m = n;
    F(i,1,n)
        F(j,1,m)a[i][j] = read(),a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];
    F(i,1,n-k+1)F(j,1,m-k+1)c[i][j] = a[i+k-1][j+k-1] - a[i+k-1][j-1] - a[i-1][j+k-1] + a[i-1][j-1];
    F(i,k,n)F(j,k,m)f[0][i][j] = max(c[i-k+1][j-k+1],max(f[0][i-1][j],f[0][i][j-1]));
    D(i,n,1)F(j,k,m)f[1][i][j] = max(c[i][j-k+1],max(f[1][i+1][j],f[1][i][j-1]));
    F(i,k,n)D(j,m,1)f[2][i][j] = max(c[i-k+1][j],max(f[2][i-1][j],f[2][i][j+1]));
    D(i,n,1)D(j,m,1)f[3][i][j] = max(c[i][j],max(f[3][i+1][j],f[3][i][j+1]));
//    F(i,1,n){
//        F(j,1,m)cout<<f[3][i][j]<<' ';
//        cout<<endl;
//    }
//    cout<<endl;
    F(i,1,n)
        F(j,1,m){
        ans = max(ans,f[0][i][j]+f[1][i+1][j]+f[2][n][j+1]);
        ans = max(ans,f[0][i][j]+f[2][i][j+1]+f[1][i+1][m]);
        ans = max(ans,f[0][n][j]+f[2][i][j+1]+f[3][i+1][j+1]);
        ans = max(ans,f[0][i][m]+f[1][i+1][j]+f[3][i+1][j+1]);
//        cout<<i<<' '<<j<<' '<<ans<<endl;
    }
    F(i,k,n-k+1)F(j,k,m-k+1){
        ans = max(ans,c[i][j]+f[0][i-1][m]+f[1][i+k][m]);
        ans = max(ans,c[i][j]+f[0][n][j-1]+f[2][n][j+k]);
    }
    printf("%lld\n",ans);
        

    return cerr<<endl<<"Time:"<<clock()<<"ms"<<endl,0;

}