まず、青木君は選ばれた \(K \times K\) 区域の中の、景観スコアの最大値を選ぶのが最適です。 よってある \(K\times K\) 区域の満足度はその区域の景観スコアの総和 から最大値を引いたものです。

\(N \times N\) のマスには \(K \times K\) 区域は \((N-K+1)^2\) 個あり、それぞれについて \(K^2\) 個のマスを全て走査するという方法は時間計算量 \(\mathrm{O}(K^2(N-K)^2)\) などになり、実行時間制限に間に合うことは難しいです。

まず、 \(K\times K\) 区域の景観スコアの総和は累積和を用いることで各区域について \(\mathrm{O}(1)\) 時間で求められます。

今度は \(K\times K\) 領域の区域の景観スコアの最大値を求めたいです。

ここでスライド最大値(最小値)と呼ばれるテクニックを利用できます。

最も基本的なスライド最大値は長さ \(N\) の配列に対して、長さ \(K\) の区間すべてについてその区間最大値を \(\mathrm{O}(N)\) で求めるようなアルゴリズムです。

今回はこれを行方向と列方向で行うことで \(K\times K\) の区域すべてについてその最大値を求めます。

まず、\(\text{row}[i][j]=\max(A_{i,j},A_{i,j+1},\ldots,A_{i,j+K-1})\) とします。

さらに、\(\text{col}[i][j]=\max(\text{row}[i][j],\text{row}[i+1][j],\ldots,\text{row}[i+K-1][j])\)

とすると、\(\text{col}[i][j]\) に\((i,j),(i,j+1),\ldots,(i,j+K-1),(i+1,j),\ldots,(i+K-1,j),\ldots,(i+K-1,j+K-1)\) の \(K \times K\) の区域についての\(A\) の最大値を求めています。

これで全体で時間計算量 \(\mathrm{O}(N^2)\) で解くことができます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<vector<int>> a(n, vector<int>(n));
    for (auto& v : a)
        for (auto& e : v) cin >> e;
    vector<vector<long long>> sum(n + 1, vector<long long>(n + 1));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) {
            sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + a[i][j];
        }
    vector<vector<int>> ma(n, vector<int>(n - k + 1));
    for (int i = 0; i < n; ++i) {
        deque<int> tmp;
        for (int j = 0; j < k - 1; ++j) {
            while (!tmp.empty() && a[i][tmp.back()] <= a[i][j]) tmp.pop_back();
            tmp.emplace_back(j);
        }
        for (int j = k - 1; j < n; ++j) {
            while (!tmp.empty() && a[i][tmp.back()] <= a[i][j]) tmp.pop_back();
            tmp.emplace_back(j);
            if (tmp.front() <= j - k) tmp.pop_front();
            ma[i][j - k + 1] = a[i][tmp.front()];
        }
    }
    long long ans = 0;
    for (int i = 0; i < n - k + 1; ++i) {
        deque<int> tmp;
        for (int j = 0; j < k - 1; ++j) {
            while (!tmp.empty() && ma[tmp.back()][i] <= ma[j][i]) tmp.pop_back();
            tmp.emplace_back(j);
        }
        for (int j = 0; j < n - k + 1; ++j) {
            while (!tmp.empty() && ma[tmp.back()][i] <= ma[j + k - 1][i]) tmp.pop_back();
            tmp.emplace_back(j + k - 1);
            if (tmp.front() < j) tmp.pop_front();
            ans = max(ans, sum[j + k][i + k] - sum[j + k][i] - sum[j][i + k] + sum[j][i] - ma[tmp.front()][i]);
        }
    }
    cout << ans << endl;
}