結果

問題 No.684 Prefix Parenthesis
コンテスト
ユーザー lam6er
提出日時 2025-04-15 23:06:48
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,584 bytes
コンパイル時間 264 ms
コンパイル使用メモリ 82,332 KB
実行使用メモリ 117,800 KB
最終ジャッジ日時 2025-04-15 23:08:50
合計ジャッジ時間 4,127 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12 WA * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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