记录编号	607102	评测结果	AAAAA
题目名称	3971.不重叠正方形	最终得分	100
用户昵称	xuyuqing	是否通过	通过
代码语言	C++	运行时间	1.939 s
提交时间	2025-10-05 16:38:08	内存使用	30.18 MiB

#include <algorithm>
#include <cstdio>
#include <iostream>
 
using namespace std;
 
const int N = 1145;
 
int n;
int m;
long long nums[N][N];
long long sqs[N][N];
long long ul[N][N];
long long ur[N][N];
long long dl[N][N];
long long dr[N][N];
long long res;
 
int main () {
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> nums[i][j];
            nums[i][j] = nums[i][j] + nums[i - 1][j] + nums[i][j - 1] - nums[i - 1][j - 1];
        }
    }
    for (int i = m; i <= n; i++) {
        for (int j = m; j <= n; j++) {
            sqs[i][j] = nums[i][j] - nums[i - m][j] - nums[i][j - m] + nums[i - m][j - m];
        }
    }
	for (int i = m; i <= n; i++) {
        for (int j = m; j <= n; j++) {
			ul[i][j] = max ({sqs[i][j], ul[i - 1][j], ul[i][j - 1]});
        }
    }
	for (int i = m; i <= n; i++) {
        for (int j = n - m + 1; j >= 1; j--) {
			ur[i][j] = max ({sqs[i][j + m - 1], ur[i - 1][j], ur[i][j + 1]});
        }
    }
	for (int i = n - m + 1; i >= 1; i--) {
		for (int j = m; j <= n; j++) {
			dl[i][j] = max ({dl[i + 1][j], dl[i][j - 1], sqs[i + m - 1][j]});
		}
	} 
	for (int i = n - m + 1; i >= 1; i--) {
		for (int j = n - m + 1; j >= 1; j--) {
			dr[i][j] = max({dr[i + 1][j], dr[i][j + 1], sqs[i + m - 1][j + m - 1]});
		}	
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i - m >= m && i + m <= n && j >= m) {
				res = max (res, sqs[i][j] + ur[i - m][1] + dr[i + 1][1]);
			}
			if (i >= m && j - m >= m && j + m - 1 <= n) {
				res = max (res, sqs[i][j] + dl[1][j - m] + dr[1][j + 1]);
			}
			if (i - 1 >= m && i + m - 1 <= n && j - 1 >= m && j + m - 1 <= n) {
				res = max (res, dr[i][j] + dl[i][j - 1] + ur[i - 1][1]);
				res = max (res, dr[i][1] + ul[i - 1][j - 1] + ur[i - 1][j]);
				res = max (res, dr[1][j] + ul[i - 1][j - 1] + dl[i][j - 1]);
				res = max (res, dr[i][j] + dl[1][j - 1] + ur[i - 1][j]);
			}
		}
	}

	cout << res << endl;
    
    return 0; 
}