ABC347F 题解

我们考虑这三个正方形的相对位置有多少种情况。

我们把正方形的顶点设为 \((x_i,y_i)\)。容易发现，放置合法当且仅当 \(\forall i \neq j, | \ x_i - x_j \ | \geq d \ \text{or} | \ y_i - y_j \ | \geq d\)。

发现这只有可能是以下两种情况。

于是便可以开始写了。

/*******************************
| Author:  DE_aemmprty
| Problem: F - Non-overlapping Squares
| Contest: AtCoder - AtCoder Beginner Contest 347
| URL:     https://atcoder.jp/contests/abc347/tasks/abc347_f
| When:    2024-03-30 21:12:33
| 
| Memory:  1024 MB
| Time:    3000 ms
*******************************/
#include <bits/stdc++.h>
using namespace std;

long long read() {
    char c = getchar();
    long long x = 0, p = 1;
    while ((c < '0' || c > '9') && c != '-') c = getchar();
    if (c == '-') p = -1, c = getchar();
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return x * p;
}

const int N = 1007;

int n, m;
long long a[N][N], b[N][N], col[N], row[N];
long long colmx[N][2], rowmx[N][2];
long long c[N][N][4];

void solve() {
    n = read(), m = read();
    for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++)
        a[i][j] = read(), a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
    for (int i = 1; i <= n - m + 1; i ++)
        for (int j = 1; j <= n - m + 1; j ++) {
            b[i][j] = a[i + m - 1][j + m - 1];
            b[i][j] -= a[i - 1][j + m - 1] + a[i + m - 1][j - 1];
            b[i][j] += a[i - 1][j - 1];
            col[j] = max(col[j], b[i][j]);
            row[i] = max(row[i], b[i][j]);
        }
    for (int i = 1; i <= n - m + 1; i ++) {
        colmx[i][0] = max(colmx[i - 1][0], col[i]);
        rowmx[i][0] = max(rowmx[i - 1][0], row[i]);
    }
    for (int i = n - m + 1; i >= 1; i --) {
        colmx[i][1] = max(colmx[i + 1][1], col[i]);
        rowmx[i][1] = max(rowmx[i + 1][1], row[i]);
    }
    for (int i = 1; i <= n - m + 1; i ++) for (int j = 1; j <= n - m + 1; j ++)
        c[i][j][0] = max(max(c[i - 1][j][0], c[i][j - 1][0]), b[i][j]);
    for (int i = n - m + 1; i; i --) for (int j = 1; j <= n - m + 1; j ++)
        c[i][j][1] = max(max(c[i + 1][j][1], c[i][j - 1][1]), b[i][j]);
    for (int i = 1; i <= n - m + 1; i ++) for (int j = n - m + 1; j; j --)
        c[i][j][2] = max(max(c[i - 1][j][2], c[i][j + 1][2]), b[i][j]);
    for (int i = n - m + 1; i; i --) for (int j = n - m + 1; j; j --)
        c[i][j][3] = max(max(c[i + 1][j][3], c[i][j + 1][3]), b[i][j]);
    long long ans = -2e9;
    for (int i = m + 1; i < n - m + 1; i ++) {
        long long mx1 = -2e9, mx2 = -2e9;
        for (int j = i + m - 1; j < n; j ++) {
            mx1 = max(mx1, col[j - m + 1]);
            mx2 = max(mx2, row[j - m + 1]);
            ans = max(ans, colmx[i - m][0] + mx1 + colmx[j + 1][1]);
            ans = max(ans, rowmx[i - m][0] + mx2 + rowmx[j + 1][1]);
        }
    }
    for (int i = n - m + 1; i > m; i --) for (int j = m + 1; j <= n - m + 1; j ++) {
        ans = max(ans, rowmx[i][1] + c[i - m][j - m][0] + c[i - m][j][2]);
        ans = max(ans, colmx[i][1] + c[j - m][i - m][0] + c[j][i - m][1]);
    }
    for (int i = m; i < n - m + 1; i ++) for (int j = m + 1; j <= n - m + 1; j ++) {
        ans = max(ans, rowmx[i - m + 1][0] + c[i + 1][j - m][1] + c[i + 1][j][3]);
        ans = max(ans, colmx[i - m + 1][0] + c[j - m][i + 1][2] + c[j][i + 1][3]);
    }
    cout << ans;
}

signed main() {
    int t = 1;
    while (t --) solve();
    return 0;
}