Overview

When we fix a row set \(R\), each column \(j\) independently determines “how many points are gained by selecting it.”
Using this property, instead of exhaustively searching all \(2^{H+W}\) combinations, we only enumerate subsets of one side (the smaller dimension) to find the maximum.

Analysis

First, if we naively enumerate all combinations of rows and columns, the number of choices is

\(2^H \times 2^W = 2^{H+W}\)

Since \(H, W \le 19\), this is up to \(2^{38}\) combinations, which is far too many to handle in time.

---

1. Fixing the row set \(R\)

When \(R\) is fixed, the total sum \(S\) of painted values is, by 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} \]

Rearranging this:

\[ S = \sum_{i \in R} \sum_{j=1}^{W} A_{i,j} + \sum_{j \in C} \left( \sum_{i=1}^{H} A_{i,j} - \sum_{i \in R} A_{i,j} \right) \]

Here, if we define the “additional score” when selecting column \(j\) as

\[ b_j = \sum_{i \notin R} A_{i,j} \]

then we can write:

\[ S = \left(\text{sum of selected rows}\right) + \sum_{j \in C} b_j \]

---

2. Optimal \(C\) for a fixed \(R\)

In the above formula, each column’s contribution is completely independent.
Therefore, for each column \(j\):

• If \(b_j > 0\), select it
• If \(b_j \le 0\), do not select it

This is optimal.

Thus, the maximum value for a fixed \(R\) is

\[ f(R) = \sum_{i \in R} \sum_{j=1}^{W} A_{i,j} + \sum_{j=1}^{W} \max(0, b_j) \]

In other words, the problem can be solved by simply:

• Enumerating all row sets \(R\)
• Computing \(b_j\) for each column each time

---

3. A naive approach is slightly too slow

If we recompute \(b_j = \sum_{i \notin R} A_{i,j}\) from scratch for each \(R\):

• Number of subsets: \(2^H\)
• Scanning all cells for each subset: \(O(HW)\)

So the total complexity is

\[ O(2^H \cdot H \cdot W) \]

While this is theoretically borderline within the constraints, it is a bit heavy in Python.
By enumerating subsets so that “consecutive subsets differ by exactly one row,” we can speed up the updates.

---

4. Using Gray code to change only one row at a time

In a standard subset enumeration, moving to the next set may change multiple rows simultaneously.
However, when enumerating in Gray code order, exactly one bit differs between consecutive sets.

That is, each step either:

• Adds one row
• Or removes one row

This means we only need to update each column’s \(b_j\) by the contribution of that single row.

---

5. How to maintain column information

For each column, we maintain

\[ \text{resid}[j] = \sum_{i \notin R} A_{i,j} \]

This represents “the score gained by selecting column \(j\) for the current \(R\).”

• Initially \(R = \emptyset\), so
  \(\text{resid}[j] = \sum_i A_{i,j}\)

• When row \(r\) is newly added to \(R\), that row is no longer part of the “additional contribution from selecting a column,” so

\[ \text{resid}[j] \mathrel{-}= A_{r,j} \]

• Conversely, when row \(r\) is removed from \(R\):

\[ \text{resid}[j] \mathrel{+}= A_{r,j} \]

Also, the optimal column value for a fixed \(R\) is

\[ \sum_j \max(0, \text{resid}[j]) \]

Instead of recomputing this from scratch each time, we can update just the “sum of positive parts” whenever a column’s value changes.

---

6. Enumerate subsets of the smaller dimension

This problem is symmetric with respect to rows and columns.
Therefore, if \(H > W\), we transpose the grid so that we always have

\[ H \le W \]

This limits the number of subsets to enumerate to \(2^{\min(H, W)}\).

The resulting complexity is

\[ O(2^{\min(H,W)} \cdot \max(H,W)) \]

Algorithm

1. If \(H > W\), transpose the grid so that \(H \le W\) always holds.
2. Compute the row totals row_total[i] and column totals total_col[j].
3. Set the initial state to \(R = \emptyset\).
   • row_sum = 0
   • resid = total_col
   • pos_sum = \sum_j \max(0, resid[j])
   • The candidate answer at this point is row_sum + pos_sum
4. Enumerate row sets \(R\) in Gray code order.
5. From the difference with the previous set, determine “which row was added/removed.”
6. For that single row:
   • Update row_sum
   • Update resid[j] for all columns
   • Update pos_sum by checking “whether the old value was positive” and “whether the new value is positive”
7. At each state, take row_sum + pos_sum as a candidate answer and track the maximum.
8. Output the maximum at the end.

Complexity

• Time complexity: \(O(2^{\min(H,W)} \cdot \max(H,W))\)
• Space complexity: \(O(HW)\)

Implementation Notes

• Transposing the grid to enumerate subsets of the smaller dimension is crucial.

• Gray code can be generated as g = k ^ (k >> 1).

• The difference between consecutive Gray codes diff = cur ^ g has exactly one bit set. Its position is extracted using bit_length() - 1.

• pos_sum is not recomputed by scanning all columns each time. Instead, for each updated column:

  • If the old value was positive, subtract it
  • If the new value is positive, add it This provides a speedup.

• The sum of values can become large, so when implementing in C++ etc., long long is required.

  Source Code

import sys

data = list(map(int, sys.stdin.buffer.read().split()))
it = iter(data)
H = next(it)
W = next(it)
A = [[next(it) for _ in range(W)] for _ in range(H)]

if H > W:
    A = [list(row) for row in zip(*A)]
    H, W = W, H

row_total = [sum(row) for row in A]
total_col = [0] * W
for i in range(H):
    row = A[i]
    for j, v in enumerate(row):
        total_col[j] += v

resid = total_col[:]
pos_sum = sum(x for x in resid if x > 0)
row_sum = 0
ans = pos_sum
cur = 0

for k in range(1, 1 << H):
    g = k ^ (k >> 1)
    diff = cur ^ g
    bit = diff.bit_length() - 1
    row = A[bit]

    if (g >> bit) & 1:
        row_sum += row_total[bit]
        for j, v in enumerate(row):
            old = resid[j]
            if old > 0:
                pos_sum -= old
            new = old - v
            resid[j] = new
            if new > 0:
                pos_sum += new
    else:
        row_sum -= row_total[bit]
        for j, v in enumerate(row):
            old = resid[j]
            if old > 0:
                pos_sum -= old
            new = old + v
            resid[j] = new
            if new > 0:
                pos_sum += new

    total = row_sum + pos_sum
    if total > ans:
        ans = total
    cur = g

print(ans)

---

This editorial was generated by gpt-5.4-high.