Overview

Given an \(N \times M\) grid of digits, the problem asks us to select a rectangle with area exactly \(K\) (\(h \times w = K\)) and find the maximum sum of digits within it.

Analysis

Key Observations

• Since the only condition on the rectangle is “area equals \(K\)”, the candidate shapes are limited to divisor pairs \((h, w)\) of \(K\) (where \(h \times w = K\)).
• For each \((h, w)\), we just need to find the maximum sum over all rectangles of that fixed size.

Why a Naive Approach Is Too Slow

• If we enumerate all rectangle positions (top-left and bottom-right) and sum up the contents each time, computing the sum of one rectangle takes \(O(hw)\).
• Doing this for all positions results in \(O(NM \cdot K)\) in the worst case, which is too slow for \(N, M \le 200\).

Solution

• Using a 2D prefix sum, we can retrieve the sum of any rectangle in \(O(1)\).
• Then, for each divisor pair of \(K\), we scan all positions and update the maximum.

Algorithm

1. Build a 2D prefix sum array \(ps\)
   • Construct \(ps[i+1][j+1]\) as the sum of the rectangle from the top-left \((0,0)\) to the bottom-right \((i,j)\).
2. Enumerate divisors \(d\) of \(K\) from \(1\) to \(\lfloor\sqrt{K}\rfloor\)
   • If \(d \mid K\), then \((h,w)=(d, K/d)\) is a candidate.
   • The rotated version \((K/d, d)\) is also a candidate (only once if they are the same).
3. For each candidate \((h,w)\), compute the maximum rectangle sum
   • Only check when \(h \le N\) and \(w \le M\).
   • With the bottom-right corner at \((i,j)\) (in terms of prefix sum array indices), the sum of the corresponding rectangle is: $\( \text{sum} = ps[i][j] - ps[i-h][j] - ps[i][j-w] + ps[i-h][j-w] \)$
   • Scan all positions and take the maximum.
4. If no valid rectangle exists, output \(-1\); otherwise, output the maximum value.

Complexity

• Time complexity:
  • Building the prefix sum: \(O(NM)\)
  • There are at most about \(\sqrt{K}\) divisor pairs, and for each pair we scan all positions in \(O(NM)\)
  • Total: \(O(NM\sqrt{K})\) (fast enough under these constraints)
• Space complexity: \(O(NM)\) (for the prefix sum array)

Implementation Notes

• Since each row of input is a string, we convert each digit to a number using list(map(int, input().strip())).

• To handle the case where no rectangle satisfying the conditions exists, we initialize the answer to -1 and only update it when a valid rectangle is found.

• When enumerating divisors, we check both \((d, K//d)\) and \((K//d, d)\) to ensure we don’t miss any orientation by swapping height and width.

  Source Code

import sys
import math

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

    ps = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(N):
        row_ps = ps[i + 1]
        prev_ps = ps[i]
        s = 0
        row = grid[i]
        for j in range(M):
            s += row[j]
            row_ps[j + 1] = prev_ps[j + 1] + s

    def max_rect(h, w):
        best = -1
        ps_local = ps
        for i in range(h, N + 1):
            psi = ps_local[i]
            psih = ps_local[i - h]
            for j in range(w, M + 1):
                v = psi[j] - psih[j] - psi[j - w] + psih[j - w]
                if v > best:
                    best = v
        return best

    ans = -1
    r = int(math.isqrt(K))
    for d in range(1, r + 1):
        if K % d != 0:
            continue
        h1, w1 = d, K // d
        if h1 <= N and w1 <= M:
            ans = max(ans, max_rect(h1, w1))
        if h1 != w1:
            h2, w2 = w1, h1
            if h2 <= N and w2 <= M:
                ans = max(ans, max_rect(h2, w2))

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.