結果

問題 No.684 Prefix Parenthesis
ユーザー lam6er
提出日時 2025-03-26 15:49:05
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,664 bytes
コンパイル時間 192 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 96,824 KB
最終ジャッジ日時 2025-03-26 15:50:12
合計ジャッジ時間 5,333 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = int(input())
s = input().strip()

# Compute l_prefix: number of '(' in the first i characters (1-based)
l_prefix = [0] * (n + 1)
for i in range(1, n + 1):
    l_prefix[i] = l_prefix[i-1] + (1 if s[i-1] == '(' else 0)

# Compute min_bal for each prefix
current_balance = 0
current_min = 0
min_bal = [0] * (n + 1)
for i in range(1, n + 1):
    c = s[i-1]
    current_balance += 1 if c == '(' else -1
    current_min = min(current_min, current_balance)
    min_bal[i] = current_min

positive = []
negative = []

for i in range(1, n + 1):
    l_i = l_prefix[i]
    r_i = i - l_i
    bal_i = l_i - r_i  # which is 2*l_i - i
    m_bal = min_bal[i]
    
    if bal_i >= 0:
        positive.append( (-m_bal, -bal_i, i, m_bal, bal_i) )
    else:
        val = m_bal - bal_i
        negative.append( (val, m_bal, bal_i) )

# Sort positive group by min_bal descending (since stored as -m_bal, sorting ascending)
positive.sort()
positive = [ (item[3], item[4]) for item in positive ]

# Sort negative group by val ascending
negative.sort()

# Process the sorted prefixes
current_balance = 0
current_min = 0

for m_bal, bal in positive:
    new_balance = current_balance + bal
    new_min = min(current_min, current_balance + m_bal)
    current_balance = new_balance
    current_min = new_min

for val, m_bal, bal in negative:
    new_balance = current_balance + bal
    new_min = min(current_min, current_balance + m_bal)
    current_balance = new_balance
    current_min = new_min

total_l = sum(l_prefix[1: n+1])
total_r = sum(i - l_prefix[i] for i in range(1, n+1))
max_pair = min(total_l, total_r) - max(0, -current_min)
max_pair = max(0, max_pair)
print(2 * max_pair)
0