結果
問題 |
No.684 Prefix Parenthesis
|
ユーザー |
![]() |
提出日時 | 2025-05-14 12:47:24 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,500 bytes |
コンパイル時間 | 203 ms |
コンパイル使用メモリ | 82,172 KB |
実行使用メモリ | 93,000 KB |
最終ジャッジ日時 | 2025-05-14 12:48:37 |
合計ジャッジ時間 | 3,824 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 3 TLE * 1 -- * 27 |
ソースコード
n = int(input()) s = input().strip() prefix = [] for i in range(n): current = s[:i+1] balance = 0 min_balance = 0 left = 0 right = 0 for c in current: if c == '(': balance += 1 left += 1 else: balance -= 1 right += 1 if balance < min_balance: min_balance = balance prefix.append((left, right, min_balance, balance)) groupA = [] groupB = [] for p in prefix: left, right, m, c = p if c >= 0: groupA.append((-m, c, left, right, m)) # sort by m descending else: groupB.append((-(c + m), c, left, right, m)) # sort by (c + m) descending groupA.sort() groupB.sort() sorted_prefix = [] for item in groupA: m_desc, c, left, right, m = item sorted_prefix.append((left, right, m, c)) for item in groupB: cm, c, left, right, m = item sorted_prefix.append((left, right, m, c)) curr_left = 0 total_pairs = 0 for left, right, m, c in sorted_prefix: if curr_left + m >= 0: matched = min(right, curr_left + left) else: # The maximum matched is (curr_left + left) + (curr_left + m) # which is curr_left + left + curr_left + m = 2*curr_left + left + m # but since curr_left + m <0, this is the deficit matched = max(0, curr_left + left + (curr_left + m)) matched = min(matched, right) total_pairs += matched curr_left += c if curr_left < 0: curr_left = 0 print(total_pairs * 2)