結果

問題 No.957 植林
ユーザー gew1fw
提出日時 2025-06-12 16:50:40
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,064 bytes
コンパイル時間 646 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 77,784 KB
最終ジャッジ日時 2025-06-12 16:51:54
合計ジャッジ時間 8,170 ms
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 16 WA * 29
権限があれば一括ダウンロードができます

ソースコード

diff #

H, W = map(int, input().split())
G = [list(map(int, input().split())) for _ in range(H)]
R = list(map(int, input().split()))
C = list(map(int, input().split()))

a = [R[i] - sum(row) for i, row in enumerate(G)]

sum_col = [0] * W
for j in range(W):
    for i in range(H):
        sum_col[j] += G[i][j]
b = [C[j] - sum_col[j] for j in range(W)]

c = [0] * W
profit = sum(max(0, b[j] + c[j]) for j in range(W))
selected = set()

while True:
    max_delta = -float('inf')
    best_i = -1
    for i in range(H):
        if i not in selected:
            current_delta = a[i]
            for j in range(W):
                prev = b[j] + c[j]
                new_val = prev + G[i][j]
                delta_j = max(0, new_val) - max(0, prev)
                current_delta += delta_j
            if current_delta > max_delta:
                max_delta = current_delta
                best_i = i
    if max_delta > 0:
        selected.add(best_i)
        for j in range(W):
            c[j] += G[best_i][j]
        profit += max_delta
    else:
        break

print(profit)
0