結果
問題 |
No.957 植林
|
ユーザー |
![]() |
提出日時 | 2025-06-12 19:03:48 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,480 bytes |
コンパイル時間 | 175 ms |
コンパイル使用メモリ | 82,596 KB |
実行使用メモリ | 87,452 KB |
最終ジャッジ日時 | 2025-06-12 19:03:57 |
合計ジャッジ時間 | 6,859 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 5 WA * 40 |
ソースコード
def main(): import sys input = sys.stdin.read().split() idx = 0 H = int(input[idx]); idx +=1 W = int(input[idx]); idx +=1 G = [] for _ in range(H): row = list(map(int, input[idx:idx+W])) idx += W G.append(row) R = list(map(int, input[idx:idx+H])) idx += H C = list(map(int, input[idx:idx+W])) idx += W # Precompute total_Gj for each column j total_Gj = [0] * W for j in range(W): for i in range(H): total_Gj[j] += G[i][j] a = [C[j] - total_Gj[j] for j in range(W)] selected = [False] * H current_sum = [0] * W profit = 0 while True: best_delta = -float('inf') best_i = -1 for i in range(H): if selected[i]: continue # Calculate delta for selecting row i row_cost = sum(G[i]) delta = (R[i] - row_cost) for j in range(W): old = max(0, a[j] + current_sum[j]) new = max(0, a[j] + current_sum[j] + G[i][j]) delta += (new - old) if delta > best_delta: best_delta = delta best_i = i if best_delta <= 0: break # Select best_i selected[best_i] = True profit += best_delta for j in range(W): current_sum[j] += G[best_i][j] print(profit) if __name__ == '__main__': main()