Overview

This problem involves selecting a rectangular region from a given grid and maximizing the sum of numbers within that region. However, the size of the region must be \(h\) (height) × \(w\) (width) such that \(h \times w = K\).

Analysis

In a naive approach, enumerating all possible rectangular regions and computing their sums results in a time complexity of \(O(N^2 M^2)\). When \(N, M\) are at most 200, this requires up to approximately \(200^4 = 1.6 \times 10^9\) computations in the worst case, which exceeds the time limit. Therefore, it is important to use a two-dimensional prefix sum to efficiently compute the sums. Additionally, by only considering pairs of divisors \((h, w)\) of \(K\), we can limit the rectangle sizes to search over.

Algorithm

1. Preprocessing: Build a two-dimensional prefix sum table pre_sum. This allows computing the sum of any rectangular region in \(O(1)\).
   • pre_sum[i][j] represents the sum of the region from the top-left \((0, 0)\) to the bottom-right \((i-1, j-1)\) of the grid.
2. Enumerating divisors: Enumerate divisors \(h\) of \(K\) and check whether \(w = K / h\) is at most \(M\). This gives us the set of rectangle sizes \((h, w)\) to search over.
3. Finding the maximum: For each size \((h, w)\), iterate over all possible starting positions \((i, j)\), compute the sum using the prefix sum, and find the maximum value to output.

Complexity

• Time complexity: \(O(d \cdot N \cdot M)\)
  • \(d\) is the number of divisors of \(K\) (at most around \(2\sqrt{K}\))
  • Since \(N, M\) are at most 200, this is sufficiently fast.
• Space complexity: \(O(N \cdot M)\)
  • Memory required for building the two-dimensional prefix sum table.

Implementation Notes

• Building the prefix sum table with 1-indexing simplifies boundary condition handling.

• If \(K\) is larger than the total grid size or no valid divisor pair exists, return \(-1\) early.

• For each divisor, scan starting positions with a double loop and compute the sum from the prefix sum in \(O(1)\).

  Source Code

def main():
    import sys
    data = sys.stdin.read().splitlines()
    if not data:
        print(-1)
        return
        
    n, m, K = map(int, data[0].split())
    grid = []
    for i in range(1, 1 + n):
        grid.append(data[i].strip())
    
    total_cells = n * m
    if K > total_cells:
        print(-1)
        return
        
    factors = []
    for h in range(1, n + 1):
        if K % h == 0:
            w = K // h
            if 1 <= w <= m:
                factors.append((h, w))
                
    if not factors:
        print(-1)
        return
        
    pre_sum = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        row_sum = 0
        for j in range(1, m + 1):
            row_sum += int(grid[i-1][j-1])
            pre_sum[i][j] = pre_sum[i-1][j] + row_sum
            
    max_score = -1
    for h, w in factors:
        for i in range(0, n - h + 1):
            for j in range(0, m - w + 1):
                total = pre_sum[i+h][j+w] - pre_sum[i][j+w] - pre_sum[i+h][j] + pre_sum[i][j]
                if total > max_score:
                    max_score = total
                    
    print(max_score)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.