Overview

For each \(K \times K\) region, Aoki’s optimal strategy is to set the cell with the maximum value within that region to \(0\).
Therefore, the satisfaction equals “region sum \(-\) region maximum,” and we need to maximize this over all possible regions.

Analysis

The key observation is the following:

• If the total of a region is \(S\) and the value Aoki sets to \(0\) is \(x\), then the result after the operation is \(S - x\).
• Since Aoki wants to minimize this, he will choose \(x\) to be as large as possible, i.e., the maximum value in the region.

Thus, the satisfaction when Takahashi places the top-left corner at \((r, c)\) is [ \text{satisfaction}(r,c)=\text{sum}{K\times K}(r,c)-\max{K\times K}(r,c) ] The final answer is the maximum of this value over all valid positions.

---

A naive approach would compute for each region: - The sum in \(K^2\) time - The maximum in \(K^2\) time

Since there are \((N-K+1)^2\) regions, this gives [ O((N-K+1)^2 \cdot K^2) ] which is close to \(O(N^4)\) in the worst case and far too slow for \(N = 1000\).

We speed up the following two computations:

1. \(K\times K\) sum: Retrieved in \(O(1)\) using a 2D prefix sum
   
2. \(K\times K\) maximum: Computed using sliding window maximum (deque) in two passes (horizontal then vertical), achieving \(O(N^2)\) overall

Combining these, we solve the entire problem in \(O(N^2)\).

Algorithm

1. Build the 2D prefix sum ps
   Set ps[i+1][j+1] to the sum from \((0,0)\) to \((i,j)\).
   Then any \(K\times K\) sum can be obtained as [ ps[r+K][c+K]-ps[r][c+K]-ps[r+K][c]+ps[r][c] ] in \(O(1)\).

2. Build ksum (\(K\times K\) sum) for all top-left positions
   The size is \(M \times M\) where \(M = N - K + 1\).

3. Build the \(K\times K\) maximum kmax (two stages)

   • First, for each row, compute the sliding window maximum of length \(K\) using a deque (hmax).
     hmax[i][c] = maximum of row \(i\) over columns \(c..c+K-1\).
   • Next, for each column \(c\), compute the sliding window maximum of length \(K\) vertically over hmax[*][c] using a deque.
     This gives kmax[r][c] = the \(K\times K\) maximum for the region with top-left \((r, c)\).

4. Compute the answer [ \max_{r,c}\bigl(ksum[r][c]-kmax[r][c]\bigr) ] Scan all positions and output the result.

---

sliding_max(arr, k) is a standard implementation using a monotonically decreasing deque: - Remove elements from the back that are less than or equal to the current element - Remove the front element if it is outside the window - The front always holds the maximum of the current window

This computes the sliding window maximum for a single array in \(O(\text{length})\) time.

Complexity

• Time complexity: \(O(N^2)\)
  (Prefix sum construction, ksum computation, horizontal sliding, vertical sliding, and the final scan are all \(O(N^2)\))
• Space complexity: \(O(N^2)\)
  (A, ps, ksum, hmax, kmax, etc.)

Implementation Notes

• Values can be up to \(10^9\), and sums can reach up to \(10^9 \cdot 10^6 = 10^{15}\), so use Python’s int (no issues with overflow).

• Consistently using \(M = N - K + 1\) for size management helps prevent indexing bugs.

• In the deque implementation, it is important to use the condition <= i - k for removing elements that have left the window.

• The initial value of ans can be set to 0 because \(A_{i,j} \ge 0\) guarantees that the satisfaction is always non-negative.

  Source Code

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()

---

This editorial was generated by gpt-5.3-codex.