Submission #51860501

---

Source Code Expand

/**
 *  @the_hyp0cr1t3
 *  30.03.2024 18:25
**/
#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n, m;
    std::cin >> n >> m;
    std::vector a(n + 1, std::vector<i64>(n + 1));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            std::cin >> a[i][j];

    i64 ans = 0;
    for (int z = 0; z < 4; z++) {
        std::vector sum(n + 1, std::vector<i64>(n + 1));
        auto p1 = sum, p2 = sum;

        auto get = [&](int i, int j) {
            return sum[i][j] - sum[i - m][j] - sum[i][j - m] + sum[i - m][j - m];
        };

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                sum[i][j] = a[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
                if (i < m or j < m) continue;
                i64 x = get(i, j);
                p1[i][j] = std::max({x, p1[i - 1][j], p1[i][j - 1]});
                p2[i][j] = std::max({x + p1[i - m][j], x + p1[i][j - m], p2[i - 1][j], p2[i][j - 1]});
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i < m or j < m) continue;
                ans = std::max(ans, get(i, j) + std::max(p2[n][j - m], p2[i - m][n]));
            }
        }

        for (int i = 1; i <= n; i++)
            std::reverse(a[i].begin() + 1, a[i].end());
        for (int i = 1; i <= n; i++)
            for (int j = i; j <= n; j++)
                std::swap(a[i][j], a[j][i]);
    }

    std::cout << ans << '\n';
}

Submission Info

Judge Result