Overview

Given an \(N \times M\) grid, the problem asks to select a rectangular region with an area (number of cells) of exactly \(K\), and maximize the sum of the numbers within that region.

Analysis

The key points for solving this problem are: “narrowing down the possible rectangle sizes” and “efficiently computing the sum within a region.”

1. Determining the Rectangle Size

Let \(h\) be the height and \(w\) be the width of the chosen rectangle. The condition is \(h \times w = K\). From this, we can observe the following: - \(h\) must be a divisor of \(K\). - To fit within the grid, we need \(1 \leq h \leq N\) and \(1 \leq w \leq M\).

The number of \((h, w)\) pairs satisfying these conditions is not very large. For example, when \(N, M \leq 200\), there are at most a few hundred combinations.

2. Computing the Sum Within a Region (Prefix Sums)

If we fix the top-left and bottom-right coordinates of the rectangle and compute the sum each time, the computational cost becomes very large. Instead, we use 2D prefix sums (or an application of 1D prefix sums). If we precompute \(P[r][c]\) as the sum from the top-left \((0, 0)\) to \((r, c)\) of the grid, then the sum of any rectangle from \((r_1, c_1)\) to \((r_2, c_2)\) can be obtained in \(O(1)\) using the following formula: $\(\text{Sum} = P[r_2][c_2] - P[r_1][c_2] - P[r_2][c_1] + P[r_1][c_1]\)$

3. Techniques to Reduce Computation

In the code for this problem, after building the 2D prefix sum, for each \(h\), we compute the prefix sum of “vertical strips of height \(h\)” and slide them horizontally to efficiently search for the maximum value.

Algorithm

1. Building the Prefix Sum: Convert the value of each cell in the grid to an integer and create a 2D prefix sum table \(P\).
2. Exhaustive Search Over Rectangle Sizes: Loop \(h\) from \(1\) to \(N\).
   • Check whether \(K\) is divisible by \(h\) and whether the quotient \(w = K/h\) is at most \(M\).
3. Updating the Maximum Score: When a valid \((h, w)\) pair is found, slide a rectangle of that size across the grid and compute the total score.
   • For every possible top row \(r\), compute the sum of the interval of height \(h\), and take horizontal differences to obtain the sum of the \(h \times w\) region.
4. Early Termination: The theoretical maximum score is \(9 \times K\). If this value is reached during the search, there is no need to search further, so we output it immediately and terminate.
5. Exception Handling: If no valid rectangle is found at all, output \(-1\).

Complexity

• Time Complexity: \(O(NM + D \cdot NM)\)
  • Here, \(D\) is the number of divisors of \(K\) (at most around \(N\)).
  • When \(N, M = 200\), \(NM = 40,000\), and the total computation stays within a few million operations, which is well within the time limit.
• Space Complexity: \(O(NM)\)
  • Memory is needed to store the prefix sum table.

Implementation Notes

• ord(c) - 48: In Python, computing the difference of character codes can sometimes be faster for numeric conversion than using int(c).

• Slicing and zip: By utilizing islice and zip in the inner loops, we compensate for Python’s loop speed and efficiently perform the sliding window computation.

• Narrowing the Range: By setting start_h = (K + M - 1) // M, we skip from the beginning any small values of \(h\) where the width \(w\) would exceed \(M\).

  Source Code

import sys
from operator import sub
from itertools import islice

def solve():
    # Read all input data and split by whitespace
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Grid dimensions N, M and the required card count K
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    grid = input_data[3:]

    # Prefix sum array P where P[r][c] stores the sum of the grid from (0,0) to (r-1, c-1)
    # This allows O(1) sum calculation for any rectangle in the grid.
    P = [[0] * (M + 1) for _ in range(N + 1)]
    for r in range(N):
        row_str = grid[r]
        Pr = P[r]
        Pr1 = P[r+1]
        row_sum = 0
        for c in range(M):
            # ord(c) - 48 is an efficient way to convert a digit character to its integer value
            row_sum += ord(row_str[c]) - 48
            Pr1[c+1] = Pr[c+1] + row_sum

    max_score = -1
    # The maximum possible score for K cards is 9 * K
    limit_score = 9 * K
    
    # A valid rectangle must have dimensions (h, w) such that h * w = K.
    # Constraints require 1 <= h <= N and 1 <= w <= M.
    # This implies h must be a divisor of K and h >= K / M.
    start_h = (K + M - 1) // M
    
    # Iterate through all possible heights h that satisfy the card count rule
    for h in range(start_h, N + 1):
        if K % h == 0:
            w = K // h
            # For a fixed rectangle size (h, w), iterate through all possible top-left corners
            for r in range(h, N + 1):
                Pr = P[r]
                Prh = P[r-h]
                
                # T[c] represents the sum of a vertical segment of height h ending at row r
                # list(map(sub, Pr, Prh)) is an efficient way to compute T[c] = P[r][c] - P[r-h][c]
                T = list(map(sub, Pr, Prh))
                
                # The sum of an h x w rectangle ending at (r, c) is T[c] - T[c-w]
                # islice and zip are used to iterate through the sliding window sums efficiently
                Tw = islice(T, w, None)
                for tw, t0 in zip(Tw, T):
                    s = tw - t0
                    if s > max_score:
                        max_score = s
                        # If the theoretical maximum score is reached, exit early
                        if max_score == limit_score:
                            print(max_score)
                            return
    
    # Print the maximum score found, or -1 if no valid rectangle exists
    print(max_score)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-thinking.