Overview

Given an \(H \times W\) grid, the problem asks you to freely choose some “rows” and “columns” and maximize the sum \(S\) of the values of the cells covered by them.

Analysis

Complementary Approach (Using the Complement)

Let \(R\) be the set of chosen rows and \(C\) be the set of chosen columns. The painted cells are those belonging to “row \(i \in R\) or column \(j \in C\).” Directly maximizing this sum \(S\) is somewhat complicated, but focusing on “the cells that are NOT painted” provides a clearer perspective.

The unpainted cells are those satisfying “row \(i \notin R\) and column \(j \notin C\),” i.e., cells at the intersection of rows and columns that were chosen for neither \(R\) nor \(C\). Let \(R'\) be the set of unchosen rows and \(C'\) be the set of unchosen columns. Denoting the sum of all cells as \(\text{TotalSum}\), we can write: $\(S = \text{TotalSum} - \sum_{i \in R'} \sum_{j \in C'} A_{i,j}\)\( To maximize \)S\(, we need to **minimize the subtracted term \)f(R’, C’) = \sum{i \in R’} \sum{j \in C’} A_{i,j}$**.

Optimizing Column Selection

Consider which columns should be included in \(C'\) when a row set \(R'\) is fixed. Let \(B_j = \sum_{i \in R'} A_{i,j}\) be “the sum of values in column \(j\) across the rows in set \(R'\).” Then: $\(f(R', C') = \sum_{j \in C'} B_j\)\( To minimize this value, we should **include in \)C’\( all columns \)j\( where \)B_j\( is negative** (if \)Bj \geq 0\(, not choosing it won't make the sum any smaller). Therefore, for a fixed \)R’\(, the minimum \)f\( is \)\sum{j=1}^{W} \min(0, B_j)$.

Reducing Computational Complexity

There are \(2^H\) possible choices for \(R'\). Computing \(B_j\) from scratch for each \(R'\) takes \(O(2^H \cdot HW)\), which is too slow for the constraints (\(H, W \leq 19\)) especially in Python.

To address this, we use Gray Code. By using Gray Code, when iterating over subsets, each transition from the previous state only requires adding or removing a single element. This allows updating \(B_j\) in \(O(W)\) per step, reducing the overall complexity to \(O(2^H \cdot W)\).

Algorithm

1. Compute the sum of all cells in the grid, total_sum.
2. To reduce computation, if \(H > W\), transpose the matrix so that \(H \le W\).
3. Use Gray Code to iterate over all subsets \(R'\) of rows in order.
   • When row \(k\) is added to (or removed from) the previous \(R'\), add (or subtract) \(A_{k,j}\) to \(B_j\) for each column \(j\).
   • Simultaneously, maintain the value of \(\sum \min(0, B_j)\) using incremental updates.
4. Among all \(R'\), find the minimum value of \(\sum \min(0, B_j)\), denoted min_f.
5. The answer is total_sum - min_f.

Complexity

• Time Complexity: \(O(2^{\min(H, W)} \cdot \max(H, W))\)
  • By assigning the smaller of rows and columns to the exponential part (\(2^{19} \approx 5.2 \times 10^5\)), the number of operations stays around \(10^7\).
• Space Complexity: \(O(HW)\)
  • Memory is needed to store the grid values.

Implementation Notes

• Transpose Handling: By swapping rows and columns when \(H > W\), we can guarantee the loop count stays around \(2^{19} \times 19\).

• Gray Code Transitions: While one approach uses i ^ (i >> 1), a more efficient method—as used in this code—identifies the changing bit via k = (i & -i).bit_length() - 1 and adds or subtracts the corresponding row.

• Incremental Updates: When the value of B[j] changes, curr_f is updated so that only negative values contribute to the sum, speeding up the inner loop.

  Source Code

import sys

def solve():
    # Set up input reading
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Read grid dimensions
    H = int(input_data[0])
    W = int(input_data[1])
    
    # Read grid values
    A = []
    idx = 2
    for i in range(H):
        A.append([int(x) for x in input_data[idx : idx + W]])
        idx += W

    # To optimize the complexity O(2^H * W), we ensure H is the smaller dimension.
    # If H > W, we transpose the grid.
    if H > W:
        A = [[A[i][j] for i in range(H)] for j in range(W)]
        H, W = W, H

    # Calculate the total sum of all values in the grid.
    total_sum = 0
    for row in A:
        for x in row:
            total_sum += x
    
    # Pre-calculate row references for faster access in the loop.
    A_rows = [row for row in A]
    
    # B[j] will store the sum of values in column j for the current subset of rows R'.
    B = [0] * W
    
    # curr_f will store the sum of negative values in B, i.e., sum(min(0, B[j])).
    # This represents the minimum sum we can get from choosing columns C' for a fixed R'.
    curr_f = 0
    
    # min_f will store the minimum value of curr_f found across all row subsets R'.
    min_f = 0
    
    # g will track the current Gray code value.
    g = 0
    
    # num_subsets is 2^H.
    num_subsets = 1 << H
    
    # We iterate through all subsets of rows using a Gray code sequence.
    # Gray code ensures that exactly one row is added or removed at each step,
    # allowing us to update the column sums B[j] and the value curr_f incrementally.
    for i in range(1, num_subsets):
        # k is the index of the bit that changes in the Gray code.
        # (i & -i).bit_length() - 1 finds the position of the rightmost set bit in i.
        k = (i & -i).bit_length() - 1
        row_k = A_rows[k]
        g ^= (1 << k)
        
        if g & (1 << k):
            # The k-th bit of g changed from 0 to 1, so we add row k.
            for j, rkj in enumerate(row_k):
                obj = B[j]
                nbj = obj + rkj
                # Update curr_f based on the change from obj to nbj.
                if nbj < 0:
                    curr_f += nbj
                if obj < 0:
                    curr_f -= obj
                B[j] = nbj
        else:
            # The k-th bit of g changed from 1 to 0, so we remove row k.
            for j, rkj in enumerate(row_k):
                obj = B[j]
                nbj = obj - rkj
                # Update curr_f based on the change from obj to nbj.
                if nbj < 0:
                    curr_f += nbj
                if obj < 0:
                    curr_f -= obj
                B[j] = nbj
        
        # Track the minimum f(R', C') across all subsets.
        if curr_f < min_f:
            min_f = curr_f
    
    # The maximum sum S is TotalSum - min(f(R', C')), where f(R', C') is the sum
    # of elements in the intersection of rows R' and columns C'.
    # This is derived from the complement of the filled cells.
    print(total_sum - min_f)

if __name__ == '__main__':
    solve()

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