よって、選んだ \(3\) つの \(M\times M\) のマス目についても、次のどちらかが成り立ちます。

• ある \(k\ (M\leq k\leq N-M)\) が存在し、\((i,j)\ (i\leq k)\) の部分と \((i,j)\ (k\lt i)\) の部分のどちらにも \(1\) つ以上の正方形が含まれ、境界にまたがる正方形は存在しない
• ある \(k\ (M\leq k\leq N-M)\) が存在し、\((i,j)\ (j\leq k)\) の部分と \((i,j)\ (k\lt j)\) の部分のどちらにも \(1\) つ以上の正方形が含まれ、境界にまたがる正方形は存在しない

また、\(2\) つの正方形が含まれる部分についても同様に考えると、最適な \(M\times M\) のマス目の取り方に関して、\(N\times N\) のマス目を \(3\) つに分割する以下の図の \(6\) 通りのいずれかの方法について、それぞれの領域に正方形が \(1\) つずつ含まれます（図中の長さの比は自由に動きます。ここでいう分割する方法は、どちらの軸に平行な線分がどのような位置関係にあるかのみで区別されます）。

これらの \(6\) 通りそれぞれについて、その形としてありえる総和の最大値を求められれば、それらの最大値が答えになります。 複数の形に合致する \(M\times M\) のマス目の取り方がある場合がありますが、最大値を求めているため問題ありません。

例えば次の \(2\) つの方針でこの問題を解くことができます。

1. それぞれの分割方法に対し、線の位置 \(O(N ^ 2)\) 通りを全探索し、それぞれの部分に含まれる \(M\times M\) マスの和としてありえる最大値を求める。
2. \(2\) つの線で区切られている領域に入る正方形を固定し、たかだか \(10\) 通りについて残りの領域の最大値を計算する。

それぞれの方針で、長方形領域に含まれるような正方形のうち合計が最大のものを求める必要があります。 この部分もいくつか方針が考えられます。

• \(2\) 次元セグメント木や \(2\) 次元 Sparse Table などを用いる。全体で \(O((N\log N) ^ 2)\) 時間などで答えを求めることができます。
• 必要となる値が限られた形で書けるので、事前に \(O(N ^ 2)\) 時間かけてこれらの値をすべて求めておくことで \(1\) 回あたり \(O(1)\) 時間となり、全体で \(O(N ^ 2)\) で答えを求められます。

\(6\) 通りの分割方法を上の図における左 \(2\) つと右 \(4\) つの \(2\) 種類に分け、それぞれ ad-hoc に求めることもできます。

実装例は以下のようになります。 \(2\) つめの方針による解法です。

#include <iostream>
#include <vector>
#include <ranges>
#include <numeric>
#include <algorithm>

int main() {
    using namespace std;
    static constexpr auto chmax{[](auto &&x, const auto &y) {
        if (x < y) x = y;
        return x;
    }};
    static constexpr auto max{[](const auto &x, const auto &y) {
        if (x < y) return y;
        return x;
    }};

    unsigned N, M;
    cin >> N >> M;

    // sum[i][j] := (i, j) を左上とする M × M 正方形内部の合計
    auto sum{[N, M] {
        vector A(N + 1, vector<unsigned long>(N + 1));
        for (auto &&row: A | views::take(N))
            for (auto &&a: row | views::take(N))
                cin >> a;

        // A[i][j] ← ∑_{i≤k,j≤l} A[k][l] とする
        for (unsigned row_index{N}; auto &&row : A | views::reverse){
        inclusive_scan(rbegin(row), rend(row), rbegin(row), plus<>{});
        if (row_index < N)
            ranges::transform(row, A[row_index + 1], begin(row), plus<>{});
        --row_index;
    }

        // sum[i][j] = A[i][j] - A[i+M][j] - A[i][j+M] + A[i+M][j+M]
        vector sum(N - M + 1, vector<unsigned long>(N - M + 1));
        for (unsigned i{}; i <= N - M; ++i)
            for (unsigned j{}; j <= N - M; ++j)
                sum[i][j] = A[i][j] - A[i + M][j] - A[i][j + M] + A[i + M][j + M];
        return sum;
    }()};

    // sum[i][j] の左上からの累積 max
    // m[i][j] = max_{k≤i,l≤j} sum[k][l]
    const auto max_UL{[](auto cells) {
        for (unsigned row_index{}; auto &&row : cells){
        inclusive_scan(begin(row), end(row), begin(row), max);
        if (row_index)
            ranges::transform(row, cells[row_index - 1], begin(row), max);
        ++row_index;
    }
        return cells;
    }};

    // 盤面を左右反転する
    const auto h_flip{[](auto &&cells) {
        for (auto &&row: cells)
            ranges::reverse(row);
        return cells;
    }};
    // 盤面を上下反転する
    const auto v_flip{[](auto &&cells) {
        ranges::reverse(cells);
        return cells;
    }};

    const auto upper_left{max_UL(sum)}; // 左上からの累積 max
    h_flip(sum); // 左右反転
    const auto upper_right{h_flip(max_UL(sum))}; // 右上からの累積 max
    v_flip(sum); // 上下反転
    const auto lower_right{h_flip(v_flip(max_UL(sum)))}; // 右下からの累積 max
    h_flip(sum); // 左右反転
    const auto lower_left{v_flip(max_UL(sum))}; // 左下からの累積 max
    v_flip(sum); // 元に戻す

    unsigned long ans{};

    // 正方形を 1 つ固定
    for (unsigned i{}; i < N - M + 1; ++i)
        for (unsigned j{}; j < N - M + 1; ++j) {
            if (M <= i && i + M < N - M + 1) // 上下に 3 つ並ぶ 中央固定
                chmax(ans, upper_left[i - M].back() + sum[i][j] + lower_right[i + M].front());
            if (M <= j && j + M < N - M + 1) // 左右に 3 つ並ぶ 中央固定
                chmax(ans, upper_left.back()[j - M] + sum[i][j] + lower_right.front()[j + M]);
            if (M <= i) { // T 型
                if (j + M < N - M + 1) // 左下
                    chmax(ans, upper_left[i - M].back() + lower_right[i][j + M] + sum[i][j]);
                if (M <= j) // 右下
                    chmax(ans, upper_left[i - M].back() + lower_left[i][j - M] + sum[i][j]);
            }
            if (M <= j) { // ト型
                if (i + M < N - M + 1) // 右下
                    chmax(ans, lower_left.front()[j - M] + lower_right[i + M][j] + sum[i][j]);
                if (M <= i) // 右上
                    chmax(ans, lower_left.front()[j - M] + upper_right[i - M][j] + sum[i][j]);
            }
            if (i + M < N - M + 1) { // 亠 型
                if (j + M < N - M + 1) // 左上
                    chmax(ans, lower_right[i + M].front() + upper_right[i][j + M] + sum[i][j]);
                if (M <= j) // 右上
                    chmax(ans, lower_right[i + M].front() + upper_left[i][j - M] + sum[i][j]);

            }
            if (j + M < N - M + 1) { // ㅓ 型
                if (i + M < N - M + 1) // 左上
                    chmax(ans, upper_right.back()[j + M] + lower_left[i + M][j] + sum[i][j]);
                if (M <= i) // 左下
                    chmax(ans, upper_right.back()[j + M] + upper_left[i - M][j] + sum[i][j]);
            }
        }

    cout << ans << endl;
    return 0;
}