結果
問題 | No.3058 Deque and Brackets |
ユーザー |
👑 |
提出日時 | 2024-06-09 14:57:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 417 ms / 2,000 ms |
コード長 | 672 bytes |
コンパイル時間 | 341 ms |
コンパイル使用メモリ | 82,320 KB |
実行使用メモリ | 117,080 KB |
最終ジャッジ日時 | 2025-03-14 20:50:24 |
合計ジャッジ時間 | 7,970 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
from heapq import heappush, heappop n = int(input()) assert 1 <= n <= 10**5 n *= 2 C = [] L = [] R = [] for _ in range(n): c, l, r = input().split() assert 1 <= int(l) <= 10**9 assert 1 <= int(r) <= 10**9 C.append(c) L.append(int(l)) R.append(int(r)) assert C.count("(") == C.count(")") == n // 2 ans = 0 lc = 0 rc = 0 hq = [] for c, l, r in zip(C[::-1], L[::-1], R[::-1]): if c == "(": lc += 1 ans += l if r > l: heappush(hq, r - l) else: rc += 1 ans += r if l > r: heappush(hq, l - r) if min(lc, rc) < len(hq): heappop(hq) ans += sum(hq) print(ans)