結果
問題 | No.3058 Deque and Brackets |
ユーザー |
![]() |
提出日時 | 2024-10-12 04:55:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 416 ms / 2,000 ms |
コード長 | 2,595 bytes |
コンパイル時間 | 283 ms |
コンパイル使用メモリ | 82,344 KB |
実行使用メモリ | 121,480 KB |
最終ジャッジ日時 | 2025-03-14 20:50:33 |
合計ジャッジ時間 | 7,512 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
""" 安いほうのスコアはあらかじめ加算しておく すると、あるほうを選ぶとスコアがもらえて、それ以外なら0点にできる --- 逆から考える ( = +1 ) = -1 とする。 左右どちらかに置くわけだが 左は、常に0以上の値 右は、常に0以下の値 である必要がある dp[i][l] = i番目まで見て、左の値がlの時の最大スコア 余り高速化できなさそう c = "(" , Lスコア ならば、左に置くのが最適 c = ")" , Rスコア ならば、右に置くのが最適 そうでない場合が曲者 ポイントを取得して置けないカッコの個数は、どうおいても一定か? - ")" を 左に置くと、左の高さを1消費 - ")" を我慢して右に置くと、右の高さが1得られて、"(" を右に置けるようになる。 考えるべきは以下の2個だけ 1. ")" で Lスコア -> できるだけ左に置きたい 2. "(" で Rスコア -> できるだけ右に置きたい 貪欲において行って、後で撤回することはできる? ")" を左に置きたいが、左の高さが0で置けない場合を考える。 この時・・・ 左に置いた ")" を撤回 -> 左の高さが1増える。右の高さも1増える。 右に置いた "(" を撤回 -> 左の高さが1増える。右の高さも1増える。 -> 左は消費してしまうので、右の高さが増える結果だけが残る。 今よりもスコアが安いのがあれば撤回するのが最適? 高さは増えたほうが嬉しいのでそれはそう 解けたかな? 1 ( 0 1 ) 1 0 """ import heapq N = int(input()) ans_base = 0 CLR = [] for i in range(2*N): C,L,R = input().split() L = int(L) R = int(R) ans_base += min(L,R) minLR = min(L,R) L -= minLR R -= minLR CLR.append( (C,L,R) ) q = [] CLR.reverse() LH = 0 RH = 0 for C,L,R in CLR: if C == "(" and R == 0: ans_base += L LH += 1 elif C == ")" and L == 0: ans_base += R RH += 1 elif C == "(": if RH > 0: RH -= 1 heapq.heappush(q,R) elif q and q[0] <= R: heapq.heappop(q) heapq.heappush(q,R) LH += 1 else: LH += 1 else: # ")" if LH > 0: LH -= 1 heapq.heappush(q , L) elif q and q[0] <= L: heapq.heappop(q) heapq.heappush(q,L) RH += 1 else: RH += 1 #print (q , LH, RH) ans = ans_base + sum(q) print (ans)