Overview

This problem asks us to find, for each \(K \times K\) region:

• The sum of values within the region
• The maximum value within the region

and then maximize \(\text{sum} - \text{maximum}\).
By computing the sum and maximum using a “sliding” technique, we can solve the entire problem in \(O(N^2)\).

Analysis

First, let’s clarify what Aoki does.

He selects one cell within the region and sets its value to \(0\), so the region’s total decreases by “the value of the chosen cell.”
Since Aoki wants to minimize the satisfaction, it is optimal for him to choose the cell with the largest value.

Therefore, the satisfaction for a given \(K \times K\) region is:

\[ \text{satisfaction} = \text{sum within the region} - \text{maximum within the region} \]

---

Why the naive approach is too slow

The number of all \(K \times K\) regions to examine is:

\[ (N-K+1)^2 \]

If we look at \(K^2\) cells for each region to compute the sum and maximum, the total complexity is:

\[ O((N-K+1)^2 K^2) \]

which is on the order of \(O(N^4)\) in the worst case.
For \(N \le 1000\), this is far too slow.

---

Key Insight

We process the 2D \(K \times K\) regions in two stages: horizontal → vertical.

1. First, consider intervals of width \(K\) for each row

For each row \(i\) and each starting column \(c\), compute:

• row_sums[i][c] = the sum of row \(i\) from column \(c\) to \(c+K-1\)
• row_maxs[i][c] = the maximum of row \(i\) from column \(c\) to \(c+K-1\)

This is a “length \(K\) interval” problem on a single row, so:

• Sum → standard sliding window
• Maximum → monotonic deque

Each row can be processed in \(O(N)\).

---

2. Then, aggregate \(K\) rows vertically

Fixing a column starting position \(c\), the total sum of a \(K \times K\) region is:

\[ \sum_{i=r}^{r+K-1} \text{row\_sums}[i][c] \]

In other words, it is “the vertical sum of row_sums[*][c] over a length \(K\) window.”

Also, the maximum of that region is:

\[ \max_{i=r}^{r+K-1} \text{row\_maxs}[i][c] \]

This is because taking the maximum of each row’s width-\(K\) interval maximum, and then taking the maximum among those, gives exactly the maximum over the entire \(K \times K\) region.

This can also be processed with a vertical sliding window:

• Sum → add/subtract while sliding vertically
• Maximum → monotonic deque

This takes \(O(N)\) per column starting position, and \(O(N^2)\) overall.

---

Concrete Example

For example, when \(K=2\), fixing a column starting position \(c\):

• For each row, precompute “the sum of 2 horizontal cells” and “the maximum of 2 horizontal cells”
• Then, aggregate 2 consecutive rows

This immediately gives us, for each \(2 \times 2\) region:

• Sum = total of the row-wise 2-cell horizontal sums
• Maximum = maximum of the row-wise 2-cell horizontal maximums

Algorithm

Let \(M = N-K+1\).

1. For each row, compute the sum and maximum of width-\(K\) intervals

For each row \(i\), create arrays of length \(M\):

• row_sums[i][c]
• row_maxs[i][c]

The computation is as follows:

• For the sum, each time the right endpoint advances by one:
  • Add the newly included value
  • Subtract the value that left the range
• For the maximum, maintain a deque in monotonically decreasing order

---

2. For each column starting position \(c\), slide vertically

Fix a column starting position \(c\) and scan rows from top to bottom.

Sum

Maintain cur_sum as:

\[ \text{the sum of } row\_sums[*][c] \text{ over the current } K \text{ rows} \]

Maximum

For row_maxs[i][c], manage the vertical length-\(K\) interval maximum using a monotonic deque.

Then, when row \(i\) is the current bottom and \(i \ge K-1\):

• Region sum = cur_sum
• Region maximum = row_maxs[dq[0]][c]

So we compute:

\[ \text{satisfaction} = \text{cur\_sum} - \text{row\_maxs[dq[0]][c]} \]

and update the overall maximum.

---

3. Output the final maximum

Complexity

• Time complexity: \(O(N^2)\)
• Space complexity: \(O(N(N-K+1)) = O(N^2)\)

Implementation Notes

• In the monotonic deque, since we want to retrieve the maximum:

  • Remove elements from the back that are less than or equal to the value being inserted
  • Remove the front element if it is outside the current range

• The total sum of values can be as large as: $\( 10^9 \times 10^6 = 10^{15} \)$ so in languages other than Python, long long or other 64-bit integer types are required.

• In this implementation, instead of storing the entire \(N \times N\) array, we build the horizontal information on the fly as each row is read. This keeps the implementation clean.

  Source Code

import sys
from collections import deque

def main():
    input = sys.stdin.buffer.readline
    N, K = map(int, input().split())
    M = N - K + 1

    row_sums = [None] * N
    row_maxs = [None] * N

    for i in range(N):
        row = list(map(int, input().split()))
        sums = [0] * M
        mxs = [0] * M

        dq = deque()
        s = 0
        for j, x in enumerate(row):
            s += x
            if j >= K:
                s -= row[j - K]

            while dq and row[dq[-1]] <= x:
                dq.pop()
            dq.append(j)
            if dq[0] <= j - K:
                dq.popleft()

            if j >= K - 1:
                idx = j - K + 1
                sums[idx] = s
                mxs[idx] = row[dq[0]]

        row_sums[i] = sums
        row_maxs[i] = mxs

    ans = 0

    for c in range(M):
        dq = deque()
        cur_sum = 0

        for i in range(N):
            cur_sum += row_sums[i][c]
            v = row_maxs[i][c]

            while dq and row_maxs[dq[-1]][c] <= v:
                dq.pop()
            dq.append(i)
            if dq[0] <= i - K:
                dq.popleft()

            if i >= K:
                cur_sum -= row_sums[i - K][c]

            if i >= K - 1:
                cand = cur_sum - row_maxs[dq[0]][c]
                if cand > ans:
                    ans = cand

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.