Overview

This problem asks you to freely choose a row set \(R\) and a column set \(C\) to maximize the total sum of cells satisfying \(i \in R\) or \(j \in C\).
The key insight is that “if we exhaustively search over subsets of one side (rows or columns), the other side can be optimized independently for each column (or each row).”

Analysis

First, writing it in the form of inclusion-exclusion: [ S = \sum{i \in R}\sum{j=1}^W A{i,j} + \sum{j \in C}\sum{i=1}^H A{i,j} - \sum{i \in R}\sum{j \in C} A_{i,j} ]

Let us reorganize this “when \(R\) is fixed.” Looking only at the contribution related to column \(j\): - If column \(j\) is not selected (\(j \notin C\)), the contribution is \(0\). - If column \(j\) is selected (\(j \in C\)), the contribution is
[ \sum{i=1}^H A{i,j} - \sum{i \in R} A{i,j} = \sum{i \notin R} A{i,j} ]

In other words, when \(R\) is fixed, each column \(j\) can independently contribute [ \max\left(0,\ \sum{i \notin R} A{i,j}\right) ] Therefore: [ S®=\sum_{i\in R}\text{rowSum}i + \sum{j=1}^W \max\left(0,\sum{i\notin R}A{i,j}\right) ] This eliminates the need to exhaustively search over \(C\).

---

Naively exhaustively searching both \((R,C)\) would require \(2^H \cdot 2^W\) combinations, which is up to \(2^{38}\) — far too many to handle in time.
Instead, we exhaustively search only the smaller dimension (since \(H,W \le 19\), this is at most \(2^{19}\)).
In the code, we transpose if necessary so that “number of rows \(N=\min(H,W)\), number of columns \(M=\max(H,W)\),” and iterate over \(2^N\).

Algorithm

1. Transpose the matrix if necessary so that \(N \le M\).
2. Precompute the full row sum for each column: col_total[j].
3. Exhaustively search over row subsets mask (from \(0\) to \(2^N-1\)).
   • row_sum_selected = total sum of selected rows.
   • Initialize col_out[j] to col_total[j], then subtract the values of the selected rows to obtain
     [ col_out[j]=\sum{i\notin R}B{i,j} ]
   • The total value is [ total = row_sum_selected + \sum_j \max(0, col_out[j]) ]
   • Update the maximum value.
4. Output the maximum value.

This formula aligns with the intuition of “paint the rows first” and “paint a column additionally only if it’s beneficial (i.e., its contribution is positive).”

Complexity

• Time complexity: \(O(2^N \cdot N \cdot M)\) (\(N=\min(H,W),\ M=\max(H,W)\))
• Space complexity: \(O(NM + M)\)

Under the constraints, \(N \le 19\), so this is sufficiently feasible.

Implementation Notes

• To exhaustively search the smaller side, it is important to create a transposed array B when H > W.

• The answer is not necessarily non-negative, but in this problem we can choose R=C=∅ to get \(S=0\), so initializing ans=0 is safe.

• Values can be on the order of \(19 \times 19 \times 10^9\), so using Python’s int avoids any overflow concerns.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]

    # Enumerate subsets of the smaller side
    if H <= W:
        N, M = H, W
        B = A
    else:
        N, M = W, H
        B = [[A[i][j] for i in range(H)] for j in range(W)]  # transpose-like view

    # B is N x M
    # Choose subset R of rows in B (size N), then best columns independently
    # S = sum_{i in R} rowSum[i] + sum_j max(0, colOutside[j])
    # where colOutside[j] = sum_{i not in R} B[i][j]
    col_total = [0] * M
    for i in range(N):
        row = B[i]
        for j in range(M):
            col_total[j] += row[j]

    ans = 0
    lim = 1 << N

    for mask in range(lim):
        row_sum_selected = 0
        col_out = col_total[:]  # start with all rows outside R

        m = mask
        i = 0
        while m:
            if m & 1:
                row = B[i]
                row_sum_selected += sum(row)
                for j in range(M):
                    col_out[j] -= row[j]
            i += 1
            m >>= 1

        total = row_sum_selected
        for v in col_out:
            if v > 0:
                total += v

        if total > ans:
            ans = total

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.3-codex.