結果
問題 |
No.1324 Approximate the Matrix
|
ユーザー |
![]() |
提出日時 | 2025-04-16 00:58:42 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,312 bytes |
コンパイル時間 | 207 ms |
コンパイル使用メモリ | 81,688 KB |
実行使用メモリ | 84,912 KB |
最終ジャッジ日時 | 2025-04-16 00:59:46 |
合計ジャッジ時間 | 4,788 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 10 WA * 32 |
ソースコード
import heapq def main(): import sys input = sys.stdin.read().split() ptr = 0 N, K = int(input[ptr]), int(input[ptr+1]) ptr +=2 A = list(map(int, input[ptr:ptr+N])) ptr +=N B = list(map(int, input[ptr:ptr+N])) ptr +=N P = [] for _ in range(N): row = list(map(int, input[ptr:ptr+N])) P.append(row) ptr +=N Q = [[0]*N for _ in range(N)] remaining_row = A.copy() remaining_col = B.copy() heap = [] for i in range(N): for j in range(N): if remaining_row[i] > 0 and remaining_col[j] > 0: marginal_cost = 1 - 2 * P[i][j] heapq.heappush(heap, (marginal_cost, -P[i][j], i, j)) while heap: mc, neg_p, i, j = heapq.heappop(heap) if remaining_row[i] <= 0 or remaining_col[j] <= 0: continue Q[i][j] +=1 remaining_row[i] -=1 remaining_col[j] -=1 new_mc = 2 * (Q[i][j] - P[i][j]) + 1 if remaining_row[i] > 0 and remaining_col[j] > 0: heapq.heappush(heap, (new_mc, -P[i][j], i, j)) total =0 for i in range(N): for j in range(N): diff = Q[i][j] - P[i][j] total += diff * diff print(total) if __name__ == "__main__": main()