Overview

Given an \(N \times N\) grid, select a \(K \times K\) sub-square, and after removing the maximum element within it, maximize the total value (= sum of the sub-square − maximum value).

Analysis

Aoki’s Optimal Strategy

Aoki changes exactly one cell within the chosen \(K \times K\) region to \(0\). Since he wants to minimize the sum within the region, his optimal strategy is to select the cell with the maximum landscape score and set it to \(0\).

Therefore, the satisfaction when choosing region \((r, c)\) is:

\[\text{satisfaction} = (\text{sum within region}) - (\text{maximum value within region})\]

Naive Approach and Its Issues

If we naively compute the sum and maximum for each \(K \times K\) region, there are \((N-K+1)^2\) regions, and computing each takes \(O(K^2)\), resulting in an overall complexity of \(O((N-K+1)^2 \cdot K^2) = O(N^2 K^2)\). When \(N = 1000\), this becomes approximately \(O(10^{12})\) in the worst case, which will TLE.

Strategy for Optimization

• Sum within a region: By precomputing a 2D prefix sum, we can obtain it in \(O(1)\).
• Maximum within a region: By using a 2D sliding window maximum, we can precompute the maximum for all regions in \(O(N^2)\).

Algorithm

1. 2D Prefix Sum (Retrieve sub-square sum in \(O(1)\))

Define \(\text{prefix}[i][j]\) as the sum from the top-left \((0,0)\) to \((i-1, j-1)\). The sum of any rectangle can be computed in \(O(1)\) using the inclusion-exclusion principle.

2. 2D Sliding Window Maximum

This is done in two stages:

Step 1: Row-wise Sliding Window Maximum

For each row \(i\), find the maximum within a window of width \(K\). Using a monotone decreasing deque, each row is processed in \(O(N)\).

\[\text{row\_max}[i][j] = \max(A[i][j], A[i][j+1], \ldots, A[i][j+K-1])\]

Step 2: Column-wise Sliding Window Maximum

For each column of \(\text{row\_max}\), find the maximum within a window of height \(K\).

\[\text{block\_max}[r][c] = \max(\text{row\_max}[r][c], \text{row\_max}[r+1][c], \ldots, \text{row\_max}[r+K-1][c])\]

This gives \(\text{block\_max}[r][c]\) as the maximum value within the \(K \times K\) region with top-left corner \((r, c)\).

3. Computing the Answer

For all regions \((r, c)\), compute the following and find the maximum:

\[\text{satisfaction} = \text{subgrid\_sum}(r, c) - \text{block\_max}[r][c]\]

Complexity

• Time complexity: \(O(N^2)\)
  • Prefix sum construction: \(O(N^2)\)
  • 2D sliding window maximum: \(O(N^2)\) (linear for each row and each column)
  • Scanning all regions: \(O((N-K+1)^2)\)
• Space complexity: \(O(N^2)\)

Implementation Notes

• Monotone deque: This is the core data structure for the sliding window maximum. The front of the deque always holds the index of the maximum value within the window. Each time a new element is added, smaller elements are removed from the back, and elements that have fallen outside the window are removed from the front.

• Splitting into two stages: Rather than directly finding the 2D maximum, by splitting into row-wise → column-wise in two passes, we reduce it to a 1D sliding window problem.

• Landscape scores are non-negative: Since Aoki must set exactly one cell to \(0\), even if all cells in a chosen region are \(0\), the satisfaction is \(0\). It never becomes negative.

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    A = []
    for i in range(N):
        row = []
        for j in range(N):
            row.append(int(input_data[idx])); idx += 1
        A.append(row)
    
    # Prefix sum for computing sum of any K×K subgrid
    # prefix[i][j] = sum of A[0..i-1][0..j-1]
    prefix = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(N):
            prefix[i+1][j+1] = A[i][j] + prefix[i][j+1] + prefix[i+1][j] - prefix[i][j]
    
    def subgrid_sum(r1, c1, r2, c2):
        # sum of A[r1..r2][c1..c2] (0-indexed, inclusive)
        return prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]
    
    # For each K×K subgrid starting at (r, c) (0-indexed),
    # the satisfaction = sum_of_subgrid - max_element_in_subgrid
    # Because Aoki will remove the maximum element.
    
    # We need to compute the maximum element in each K×K subgrid efficiently.
    # We can use 2D sliding window maximum.
    
    # Step 1: For each row, compute sliding window max of width K
    # row_max[i][j] = max of A[i][j..j+K-1]
    
    from collections import deque
    
    # Row-wise sliding window max
    # row_max[i][j] for j in range(N-K+1): max of A[i][j..j+K-1]
    row_max = [[0] * (N - K + 1) for _ in range(N)]
    
    for i in range(N):
        dq = deque()
        for j in range(N):
            while dq and dq[0] < j - K + 1:
                dq.popleft()
            while dq and A[i][dq[-1]] <= A[i][j]:
                dq.pop()
            dq.append(j)
            if j >= K - 1:
                row_max[i][j - K + 1] = A[i][dq[0]]
    
    # Step 2: For each column of row_max, compute sliding window max of height K
    # block_max[r][c] = max of row_max[r..r+K-1][c] = max of K×K block starting at (r,c)
    
    num_cols = N - K + 1
    num_rows = N - K + 1
    block_max = [[0] * num_cols for _ in range(num_rows)]
    
    for c in range(num_cols):
        dq = deque()
        for i in range(N):
            while dq and dq[0] < i - K + 1:
                dq.popleft()
            while dq and row_max[dq[-1]][c] <= row_max[i][c]:
                dq.pop()
            dq.append(i)
            if i >= K - 1:
                block_max[i - K + 1][c] = row_max[dq[0]][c]
    
    # Now compute the answer
    ans = -1
    for r in range(num_rows):
        for c in range(num_cols):
            s = subgrid_sum(r, c, r + K - 1, c + K - 1)
            satisfaction = s - block_max[r][c]
            if satisfaction > ans:
                ans = satisfaction
    
    print(ans)

main()

---

This editorial was generated by claude4.6opus-thinking.