Overview

Given an \(H \times W\) grid, we choose a set of rows \(R\) and a set of columns \(C\), and maximize the sum of values of cells where \(i \in R\) or \(j \in C\). We enumerate all subsets of the smaller dimension and greedily determine the other dimension.

Analysis

The Problem with the Naive Approach

Since there are \(2^H\) ways to choose \(R\) and \(2^W\) ways to choose \(C\), enumerating all pairs \((R, C)\) would require \(2^{H+W}\) combinations (up to \(2^{38}\)), which is far too slow.

Key Insight: Fixing the Rows Allows Greedy Column Selection

We use the following decomposition:

\[S = \underbrace{\sum_{i \in R} \sum_{j=1}^{W} A_{i,j}}_{\text{sum of selected rows}} + \sum_{j \in C} \underbrace{\left(\sum_{i=1}^{H} A_{i,j} - \sum_{i \in R} A_{i,j}\right)}_{\text{gain from adding column } j}\]

When \(R\) is fixed, the increase in value from including column \(j\) in \(C\) is:

\[\text{benefit}(j) = \text{col\_sum}[j] - \sum_{i \in R} A_{i,j}\]

This is the “total sum of column \(j\)” minus the “portion already covered by \(R\).” If this value is positive, we should select column \(j\); otherwise, we should not.

In other words, once \(R\) is determined, \(C\) can be greedily determined in \(O(W)\).

Choosing Which Dimension to Enumerate

Enumerating all subsets of \(R\) takes \(O(2^H)\), and enumerating all subsets of \(C\) takes \(O(2^W)\). We can reduce the computation by enumerating the smaller dimension. Letting \(n = \min(H, W)\) and \(m = \max(H, W)\), the problem can be solved in \(O(2^n \cdot m)\).

Algorithm

Assume \(H \leq W\) (otherwise, swap the roles of rows and columns).

1. Precomputation: Compute the sum of each row \(\text{row\_sum}[i]\) and the sum of each column \(\text{col\_sum}[j]\).

2. Cumulative computation over subsets (LSB technique): For each bitmask \(\text{mask}\) (representing a subset of rows), compute:

   • \(\text{rss}[\text{mask}]\): the sum of all elements in the selected rows
   • \(\text{cp}[j][\text{mask}]\): the sum of elements in column \(j\) among the selected rows (the overlapping portion)

These are computed recurrently in \(O(1)\) using the lowest set bit (LSB) of the mask: $\(\text{rss}[\text{mask}] = \text{rss}[\text{mask} \oplus \text{lsb}] + \text{row\_sum}[\text{bit}]\)$

1. Iterate over all masks: For each \(\text{mask}\):
   • Start with \(s = \text{rss}[\text{mask}]\)
   • For each column \(j\), compute \(\text{benefit} = \text{col\_sum}[j] - \text{cp}[j][\text{mask}]\), and add it to \(s\) if positive
   • The maximum value of \(s\) across all masks is the answer

Concrete Example

For a \(2 \times 2\) grid with \(A = \begin{pmatrix} 5 & -3 \\ -2 & 4 \end{pmatrix}\):

• When selecting \(R = \{1\}\) (row 1 only), \(\text{rss} = 5 + (-3) = 2\)
• Benefit of column 1: \(\text{col\_sum}[1] - A_{1,1} = (5-2) - 5 = -2\) (do not select)
• Benefit of column 2: \(\text{col\_sum}[2] - A_{1,2} = (-3+4) - (-3) = 4\) (select)
• \(S = 2 + 4 = 6\) (cells \((1,1), (1,2), (2,2)\) are painted, with total \(5-3+4=6\))

Complexity

• Time complexity: \(O(2^n \cdot m)\) (\(n = \min(H, W)\), \(m = \max(H, W)\))
  • When \(n = 19, m = 19\), this is approximately \(10^7\), which is fast enough
• Space complexity: \(O(2^n \cdot m)\) (for the cp or rp array)

Implementation Notes

• Enumerate the smaller dimension: By choosing the smaller of \(H\) and \(W\) for subset enumeration, we keep the computation at \(2^{19} \cdot 19 \approx 10^7\). Enumerating the larger dimension would significantly increase the computation even under the same constraints.

• Recurrent computation using LSB: The lowest set bit of mask mask is obtained via mask & (-mask), and results from the mask with one fewer bit are reused, making the precomputation efficient.

• Initialize the answer to 0: When \(R = C = \emptyset\) (nothing is painted), \(S = 0\), so even if only negative values are achievable, 0 is the answer.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    H = int(data[idx]); idx += 1
    W = int(data[idx]); idx += 1
    A = []
    for i in range(H):
        row = [int(data[idx + j]) for j in range(W)]
        idx += W
        A.append(row)

    # Always enumerate over the smaller dimension
    if H <= W:
        # Enumerate subsets of rows
        n, m = H, W
        row_sum = [sum(A[i]) for i in range(n)]
        col_sum = [sum(A[i][j] for i in range(n)) for j in range(m)]

        size = 1 << n
        rss = [0] * size
        # cp[j][mask] = sum of A[i][j] for i in mask
        cp = [[0] * size for _ in range(m)]

        for mask in range(1, size):
            lsb = mask & (-mask)
            bit = lsb.bit_length() - 1
            prev = mask ^ lsb
            rss[mask] = rss[prev] + row_sum[bit]
            for j in range(m):
                cp[j][mask] = cp[j][prev] + A[bit][j]

        ans = 0
        for mask in range(size):
            s = rss[mask]
            for j in range(m):
                benefit = col_sum[j] - cp[j][mask]
                if benefit > 0:
                    s += benefit
            if s > ans:
                ans = s

        print(ans)
    else:
        # Enumerate subsets of columns
        n, m = W, H
        col_sum = [sum(A[i][j] for i in range(m)) for j in range(n)]
        row_sum = [sum(A[i]) for i in range(m)]

        size = 1 << n
        css = [0] * size
        # rp[i][mask] = sum of A[i][j] for j in mask
        rp = [[0] * size for _ in range(m)]

        for mask in range(1, size):
            lsb = mask & (-mask)
            bit = lsb.bit_length() - 1
            prev = mask ^ lsb
            css[mask] = css[prev] + col_sum[bit]
            for i in range(m):
                rp[i][mask] = rp[i][prev] + A[i][bit]

        ans = 0
        for mask in range(size):
            s = css[mask]
            for i in range(m):
                benefit = row_sum[i] - rp[i][mask]
                if benefit > 0:
                    s += benefit
            if s > ans:
                ans = s

        print(ans)

main()

---

This editorial was generated by claude4.6opus-thinking.