結果

問題 No.684 Prefix Parenthesis
コンテスト
ユーザー qwewe
提出日時 2025-04-24 12:23:27
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,500 bytes
コンパイル時間 190 ms
コンパイル使用メモリ 82,512 KB
実行使用メモリ 94,768 KB
最終ジャッジ日時 2025-04-24 12:25:25
合計ジャッジ時間 3,817 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
0