Overview

On an \(N \times M\) grid, select a rectangular region consisting of exactly \(K\) cells and maximize the sum of the numbers contained within it.

Analysis

In this problem, the area of the chosen rectangular region must be exactly \(K\). In other words, for the height \(h\) and width \(w\), the condition \(h \times w = K\) must hold.

The first idea that comes to mind is to try all possible combinations of \(h, w\), but we can narrow down the candidates by exhaustively searching through the divisors of \(K\). If \(h\) is a divisor of \(K\), then \(w = K/h\), and we just need to check whether \(w\) is at most \(M\).

Next, for each pair \((h, w)\), we compute the sum of the \(h \times w\) rectangle at every position within the grid and record the maximum value. However, if we naively sum the elements inside the rectangle each time, the computational cost becomes too large to fit within the time limit.

Therefore, by using a two-dimensional prefix sum (also known as 2D cumulative sum), we can efficiently compute the sum of any rectangular range. This significantly reduces the overall computational complexity.

Algorithm

1. Input Processing:

   • Read the grid as a two-dimensional array of numbers.

2. Enumeration of Divisors:

   • Iterate \(h\) from \(1\) to \(N\). If \(K\) is divisible by \(h\), set \(w = K/h\).
   • If \(w \leq M\), save \((h, w)\) as a candidate.

3. Construction of the 2D Prefix Sum:

   • This is the extension of the standard prefix sum to two dimensions.
   • acc[i][j] stores the sum of the rectangular region from \((0, 0)\) to \((i-1, j-1)\).
   • Update formula: $\( \text{acc}[i][j] = \text{grid}[i-1][j-1] + \text{acc}[i-1][j] + \text{acc}[i][j-1] - \text{acc}[i-1][j-1] \)$

4. Function to Retrieve the Sum of an Arbitrary Rectangle:

   • The function get_sum(x1, y1, x2, y2) retrieves the sum from \((x1, y1)\) to \((x2-1, y2-1)\) in \(O(1)\).

5. Exhaustive Search and Maximum Value Update:

   • For each candidate \((h, w)\), compute the rectangle sum for all possible positions \((i, j)\) within the grid, and update the maximum value.

6. Output:

   • If there are no candidates, output \(-1\).
   • Otherwise, output the maximum score obtained.

Complexity

• Time complexity: \(O(d(K) \cdot N \cdot M)\)
  (where \(d(K)\) is the number of divisors of \(K\), which is at most a few hundred)
• Space complexity: \(O(N \cdot M)\)
  (the size of the 2D prefix sum table)

Implementation Notes

• Be careful with index management for the 2D prefix sum (it is common to use 1-indexed)

• Note that the arguments of get_sum use “half-open intervals” (the endpoint is not included)

• Do not forget to handle the case where no pair satisfying \(h \times w = K\) exists

  Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    
    # グリッド読み込み
    S = data[3:3+N]
    grid = []
    for i in range(N):
        row = list(map(int, list(S[i])))
        grid.append(row)
    
    # 約数列挙: K = h * w となる h, w の組を求める
    candidates = []
    for h in range(1, N+1):
        if K % h == 0:
            w = K // h
            if w <= M:
                candidates.append((h, w))
    
    if not candidates:
        print(-1)
        return
    
    # 二次元累積和の構築
    # acc[i][j] = (0,0) から (i-1,j-1) までの長方形和
    acc = [[0]*(M+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(M):
            acc[i+1][j+1] = grid[i][j] + acc[i+1][j] + acc[i][j+1] - acc[i][j]
    
    def get_sum(x1, y1, x2, y2):
        # (x1,y1) から (x2-1,y2-1) の長方形和を返す
        return acc[x2][y2] - acc[x1][y2] - acc[x2][y1] + acc[x1][y1]
    
    max_score = -1
    for h, w in candidates:
        for i in range(N - h + 1):
            for j in range(M - w + 1):
                current = get_sum(i, j, i+h, j+w)
                if current > max_score:
                    max_score = current
    
    print(max_score)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.