結果

問題 No.957 植林
ユーザー gew1fw
提出日時 2025-06-12 21:32:30
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,942 bytes
コンパイル時間 280 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 92,416 KB
最終ジャッジ日時 2025-06-12 21:33:46
合計ジャッジ時間 4,270 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    H = int(input[ptr])
    ptr += 1
    W = int(input[ptr])
    ptr += 1

    G = []
    for _ in range(H):
        row = list(map(int, input[ptr:ptr + W]))
        ptr += W
        G.append(row)
    
    R = list(map(int, input[ptr:ptr + H]))
    ptr += H
    C = list(map(int, input[ptr:ptr + W]))
    ptr += W

    # Precompute a_i = R_i - sum_j G[i][j]
    a = [R[i] - sum(G[i]) for i in range(H)]
    # Precompute b_j = C_j - sum_i G[i][j]
    b = [C[j] - sum(G[i][j] for i in range(H)) for j in range(W)]
    # Precompute d_{i,j} = max(-G[i][j], 0)
    d = [[max(-g, 0) for g in row] for row in G]
    # Precompute c_{i,j} = max(G[i][j], 0)
    c = [[max(g, 0) for g in row] for row in G]

    # Compute a'_i = a_i - sum_j d[i][j]
    a_prime = [a[i] - sum(d[i][j] for j in range(W)) for i in range(H)]
    # Compute b'_j = b_j - sum_i d[i][j]
    b_prime = [b[j] - sum(d[i][j] for i in range(H)) for j in range(W)]

    max_total = 0

    for mask_rows in range(0, 1 << H):
        for mask_cols in range(0, 1 << W):
            total = 0
            for i in range(H):
                if (mask_rows >> i) & 1:
                    total += a_prime[i]
            for j in range(W):
                if (mask_cols >> j) & 1:
                    total += b_prime[j]
            for i in range(H):
                for j in range(W):
                    if (mask_rows >> i) & 1 and (mask_cols >> j) & 1:
                        total += c[i][j]
            current = 0
            for i in range(H):
                for j in range(W):
                    if not ((mask_rows >> i) & 1) and not ((mask_cols >> j) & 1):
                        if G[i][j] < 0:
                            current += (-G[i][j])
            total += current
            if total > max_total:
                max_total = total
    print(max_total)

if __name__ == '__main__':
    main()
0