概要

各 \(K \times K\) 区域について、青木君は「その中の最大値マス」を \(0\) にするのが最適です。
したがって満足度は「区域和 \(-\) 区域内最大値」となり、これを全区域で最大化すればよい問題です。

考察

重要な観察は次の1点です。

• ある区域の合計を \(S\)、その中で青木君が \(0\) にする値を \(x\) とすると、操作後は \(S-x\)。
• 青木君はこれを最小化したいので、\(x\) はできるだけ大きい値、つまり区域内最大値を選ぶ。

よって、高橋君が top-left を \((r,c)\) にした区域の満足度は [ \text{satisfaction}(r,c)=\text{sum}{K\times K}(r,c)-\max{K\times K}(r,c) ] です。
最終的な答えは、この値の最大です。

---

素朴にやると、各区域ごとに - 和を \(K^2\) で計算 - 最大値も \(K^2\) で計算

となり、区域数は \((N-K+1)^2\) 個なので [ O((N-K+1)^2 \cdot K^2) ] 最悪で \(O(N^4)\) 近くなり、\(N=1000\) では到底間に合いません。

そこで以下の2つを高速化します。

1. \(K\times K\) 和：2次元累積和で \(O(1)\) 取得
   
2. \(K\times K\) 最大値：スライディングウィンドウ最大（deque）を横→縦の2段で行い全体 \(O(N^2)\)

この組み合わせで全体を \(O(N^2)\) で解けます。

アルゴリズム

1. 2次元累積和 ps を作る
   ps[i+1][j+1] を \((0,0)\) から \((i,j)\) までの和にする。
   すると任意の \(K\times K\) 和は [ ps[r+K][c+K]-ps[r][c+K]-ps[r+K][c]+ps[r][c] ] で \(O(1)\)。

2. 全 top-left に対する ksum（\(K\times K\) 和）を作る
   サイズは \(M \times M\)（\(M=N-K+1\)）。

3. \(K\times K\) 最大値 kmax を作る（2段階）

   • まず各行ごとに、長さ \(K\) の区間最大を deque で求める（hmax）。
     hmax[i][c] = 行 \(i\) の列 \(c..c+K-1\) の最大。
   • 次に各列 \(c\) について、hmax[*][c] に対し縦方向長さ \(K\) の区間最大を deque で求める。
     これで kmax[r][c] = 区域 \((r,c)\) の \(K\times K\) 最大値。

4. 答えを計算 [ \max_{r,c}\bigl(ksum[r][c]-kmax[r][c]\bigr) ] を走査して出力。

---

sliding_max(arr, k) は単調減少 deque を使う定番実装です。
- 後ろから「自分以下」を消す
- 先頭が窓外なら消す
- 先頭が常に現在窓の最大

これにより1配列あたり \(O(\text{長さ})\) で区間最大列が作れます。

計算量

• 時間計算量: \(O(N^2)\)
  （累積和構築、ksum 作成、横スライド、縦スライド、最終走査のすべてが \(O(N^2)\)）
• 空間計算量: \(O(N^2)\)
  （A, ps, ksum, hmax, kmax など）

実装のポイント

• 値は最大で \(10^9\)、和は最大で \(10^9 \cdot 10^6 = 10^{15}\) 規模になるため、Python の int で扱う（問題なし）。

• M = N-K+1 のサイズ管理を統一すると添字バグを防げます。

• deque 実装では「窓外削除条件」を <= i-k にするのが重要です。
  

• ans 初期値を 0 にできるのは、\(A_{i,j}\ge 0\) なので満足度も常に非負だからです。

  ソースコード

import sys
from collections import deque

def sliding_max(arr, k):
    dq = deque()
    res = []
    for i, x in enumerate(arr):
        while dq and arr[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        while dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            res.append(arr[dq[0]])
    return res

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]

    # Prefix sum for KxK sums
    ps = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N):
        row_ps = 0
        pi1 = ps[i + 1]
        pi = ps[i]
        ai = A[i]
        for j in range(N):
            row_ps += ai[j]
            pi1[j + 1] = pi[j + 1] + row_ps

    M = N - K + 1

    # KxK sum for each top-left
    ksum = [[0] * M for _ in range(M)]
    for r in range(M):
        r2 = r + K
        pr = ps[r]
        pr2 = ps[r2]
        row = ksum[r]
        for c in range(M):
            c2 = c + K
            row[c] = pr2[c2] - pr[c2] - pr2[c] + pr[c]

    # Horizontal sliding max of width K for each row
    hmax = [sliding_max(A[i], K) for i in range(N)]  # N x M

    # Vertical sliding max of height K over hmax to get KxK max for each top-left
    kmax = [[0] * M for _ in range(M)]
    for c in range(M):
        col = [hmax[r][c] for r in range(N)]
        v = sliding_max(col, K)  # length M
        for r in range(M):
            kmax[r][c] = v[r]

    ans = 0
    for r in range(M):
        sr = ksum[r]
        mr = kmax[r]
        for c in range(M):
            val = sr[c] - mr[c]
            if val > ans:
                ans = val

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.3-codex によって生成されました。