結果
問題 | No.1767 BLUE to RED |
ユーザー |
|
提出日時 | 2024-07-05 09:39:47 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 878 bytes |
コンパイル時間 | 75 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 247,048 KB |
最終ジャッジ日時 | 2024-07-05 09:40:08 |
合計ジャッジ時間 | 16,201 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 9 TLE * 3 -- * 9 |
ソースコード
import sysfrom heapq import heappush, heappop, heapifyinput = sys.stdin.buffer.readlineN, M = map(int, input().split())A = list(map(int, input().split()))B = list(map(int, input().split()))G = [[] for _ in range(N + M + 1)]S = [(x, 1) for x in A] + [(x, 0) for x in B]S.sort()for i, (x, c) in enumerate(S, 1):if c:G[0].append((i, 0))G[i].append((0, 0))for i in range(1, N + M):G[i].append((i + 1, S[i][0] - S[i - 1][0]))G[i + 1].append((i, S[i][0] - S[i - 1][0]))# https://tjkendev.github.io/procon-library/python/graph/min_st_prim.htmlused = [0] * (N + M + 1)que = [(c, w) for w, c in G[0]]used[0] = 1heapify(que)ans = 0while que:cv, v = heappop(que)if used[v]:continueused[v] = 1ans += cvfor w, c in G[v]:if used[w]:continueheappush(que, (c, w))print(ans)