概要

行集合 \(R\) と列集合 \(C\) を自由に選んで、\(i \in R\) または \(j \in C\) を満たすマスの総和を最大化する問題です。
ポイントは「片側（行か列）の部分集合を全探索し、もう片側は各列（各行）ごとに独立に最適化できる」と気づくことです。

考察

まず、包除原理の形で書くと [ 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} ] です。

これを「\(R\) を固定したとき」に整理します。列 \(j\) に関する寄与だけ見ると、 - 列 \(j\) を選ばない（\(j \notin C\)）なら寄与は \(0\) - 列 \(j\) を選ぶ（\(j \in C\)）なら寄与は
[ \sum{i=1}^H A{i,j} - \sum{i \in R} A{i,j} = \sum{i \notin R} A{i,j} ] となります。

つまり、\(R\) 固定なら列 \(j\) は独立に [ \max\left(0,\ \sum{i \notin R} A{i,j}\right) ] を足せばよいです。よって [ S®=\sum_{i\in R}\text{rowSum}i + \sum{j=1}^W \max\left(0,\sum{i\notin R}A{i,j}\right) ] となり、\(C\) を全探索する必要がなくなります。

---

素朴に \((R,C)\) を両方全探索すると \(2^H \cdot 2^W\) 通りで、最大で \(2^{38}\) と到底間に合いません。
そこで、小さい方の次元だけを全探索します（\(H,W \le 19\) なので最大でも \(2^{19}\)）。
コードでは、必要なら転置して「行数 \(N=\min(H,W)\)、列数 \(M=\max(H,W)\)」の形にして、\(2^N\) を回しています。

アルゴリズム

1. 必要なら行列を見かけ上転置して、\(N \le M\) にする。
2. 各列の全行合計 col_total[j] を前計算する。
3. 行部分集合 mask（\(0\) から \(2^N-1\)）を全探索する。
   • row_sum_selected = 選んだ行の総和。
   • col_out[j] を最初 col_total[j] にして、選んだ行の値を引くことで
     [ col_out[j]=\sum{i\notin R}B{i,j} ] を作る。
   • 合計値は [ total = row_sum_selected + \sum_j \max(0, col_out[j]) ]
   • 最大値を更新。
4. 最大値を出力。

この式は「行を先に塗る」「列は追加で得なら塗る（正なら塗る）」という直感と一致しています。

計算量

• 時間計算量: \(O(2^N \cdot N \cdot M)\)（\(N=\min(H,W),\ M=\max(H,W)\)）
• 空間計算量: \(O(NM + M)\)

制約下では \(N \le 19\) なので十分実行可能です。

実装のポイント

• 小さい側を全探索するため、H > W のときは転置風の配列 B を作るのが重要です。

• 答えは 0 以上とは限りませんが、この問題では R=C=∅ で \(S=0\) が選べるため、初期値 ans=0 で安全です。

• 値は最大で \(19 \times 19 \times 10^9\) 規模になるので、Python の int を使えばオーバーフローの心配はありません。

  ソースコード

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()

---

この解説は gpt-5.3-codex によって生成されました。