結果

問題 No.957 植林
ユーザー lam6er
提出日時 2025-03-31 17:59:59
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,537 bytes
コンパイル時間 191 ms
コンパイル使用メモリ 82,912 KB
実行使用メモリ 86,948 KB
最終ジャッジ日時 2025-03-31 18:00:53
合計ジャッジ時間 8,040 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 WA * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    H = int(input[idx])
    W = int(input[idx+1])
    idx +=2
    
    G = []
    row_sum = [0]*H
    for i in range(H):
        row = list(map(int, input[idx:idx+W]))
        G.append(row)
        row_sum[i] = sum(row)
        idx += W
    
    R = list(map(int, input[idx:idx+H]))
    idx += H
    C = list(map(int, input[idx:idx+W]))
    idx += W
    
    a = [R[i] - row_sum[i] for i in range(H)]
    
    col_sum = [0]*W
    for j in range(W):
        s = 0
        for i in range(H):
            s += G[i][j]
        col_sum[j] = s
    
    b = [C[j] - col_sum[j] for j in range(W)]
    
    sum_j = [0]*W
    current_profit = 0
    selected = [False]*H
    
    while True:
        max_delta = -float('inf')
        best_i = -1
        
        for i in range(H):
            if selected[i]:
                continue
            
            delta = a[i]
            for j in range(W):
                current = sum_j[j] + b[j]
                new_sum = sum_j[j] + G[i][j]
                new = new_sum + b[j]
                
                delta += max(0, new) - max(0, current)
            
            if delta > max_delta:
                max_delta = delta
                best_i = i
        
        if max_delta <= 0:
            break
        
        current_profit += max_delta
        selected[best_i] = True
        for j in range(W):
            sum_j[j] += G[best_i][j]
    
    print(current_profit)

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