結果
問題 |
No.684 Prefix Parenthesis
|
ユーザー |
![]() |
提出日時 | 2025-04-15 23:02:16 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,584 bytes |
コンパイル時間 | 132 ms |
コンパイル使用メモリ | 82,376 KB |
実行使用メモリ | 117,860 KB |
最終ジャッジ日時 | 2025-04-15 23:04:10 |
合計ジャッジ時間 | 4,029 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 12 WA * 19 |
ソースコード
n = int(input()) s = input().strip() # Precompute for each i (1-based) the min_bal and delta min_bal = [0] * (n + 1) delta = [0] * (n + 1) current_balance = 0 current_min = 0 prefix_L = [0] * (n + 1) prefix_R = [0] * (n + 1) for i in range(1, n + 1): c = s[i-1] if c == '(': current_balance += 1 prefix_L[i] = prefix_L[i-1] + 1 prefix_R[i] = prefix_R[i-1] else: current_balance -= 1 prefix_L[i] = prefix_L[i-1] prefix_R[i] = prefix_R[i-1] + 1 current_min = min(current_min, current_balance) min_bal[i] = current_min delta[i] = current_balance # Collect all S_i (1-based) segments = [] for i in range(1, n+1): L = prefix_L[i] R = prefix_R[i] seg_min_bal = min_bal[i] seg_delta = delta[i] segments.append( (i, seg_min_bal, seg_delta, L, R) ) # Split into two groups positive = [] negative = [] for seg in segments: i, seg_min, d, L, R = seg if d >= 0: positive.append( (seg_min, d, L, R) ) else: negative.append( (seg_min, d, L, R) ) # Sort positive group by seg_min ascending positive.sort(key=lambda x: x[0]) # Sort negative group by (d - seg_min) descending negative.sort(key=lambda x: -(x[1] - x[0])) # Concatenate the groups sorted_segments = positive + negative # Process the sorted segments total = 0 balance = 0 for seg in sorted_segments: seg_min, d, L, R = seg if balance + seg_min >= 0: total += R balance += d else: add = max(0, balance + L + seg_min) total += add balance += d print(total * 2)