結果
問題 |
No.957 植林
|
ユーザー |
![]() |
提出日時 | 2025-04-15 23:09:03 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,759 bytes |
コンパイル時間 | 536 ms |
コンパイル使用メモリ | 81,968 KB |
実行使用メモリ | 92,868 KB |
最終ジャッジ日時 | 2025-04-15 23:11:26 |
合計ジャッジ時間 | 6,167 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 1 WA * 4 TLE * 1 -- * 39 |
ソースコード
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 # Compute A and B A = [] for i in range(H): sum_g = sum(G[i][j] for j in range(W)) A.append(R[i] - sum_g) B = [] for j in range(W): sum_g = sum(G[i][j] for i in range(H)) B.append(C[j] - sum_g) max_profit = 0 def compute_profit(S, T): sum_A = sum(A[i] for i in S) sum_B = sum(B[j] for j in T) sum_G = 0 for i in S: for j in T: sum_G += G[i][j] return sum_A + sum_B + sum_G # Case 1: S and T are empty current_S = set() current_T = set() profit = compute_profit(current_S, current_T) max_profit = max(max_profit, profit) # Case 2: Initialize with each row for i in range(H): current_S = {i} current_T = set() while True: # Compute new_T new_T = set() for j in range(W): sum_g = sum(G[i_row][j] for i_row in current_S) if B[j] + sum_g > 0: new_T.add(j) # Compute new_S new_S = set() for i_row in range(H): sum_g = sum(G[i_row][j] for j in new_T) if A[i_row] + sum_g > 0: new_S.add(i_row) if new_S == current_S and new_T == current_T: break current_S, current_T = new_S, new_T profit = compute_profit(current_S, current_T) max_profit = max(max_profit, profit) # Case 3: Initialize with each column for j in range(W): current_T = {j} current_S = set() while True: # Compute new_S new_S = set() for i_row in range(H): sum_g = sum(G[i_row][j_col] for j_col in current_T) if A[i_row] + sum_g > 0: new_S.add(i_row) # Compute new_T new_T = set() for j_col in range(W): sum_g = sum(G[i_row][j_col] for i_row in new_S) if B[j_col] + sum_g > 0: new_T.add(j_col) if new_S == current_S and new_T == current_T: break current_S, current_T = new_S, new_T profit = compute_profit(current_S, current_T) max_profit = max(max_profit, profit) print(max_profit) if __name__ == '__main__': main()