結果

問題 No.684 Prefix Parenthesis
ユーザー qwewe
提出日時 2025-04-24 12:20:43
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,344 bytes
コンパイル時間 261 ms
コンパイル使用メモリ 82,356 KB
実行使用メモリ 97,044 KB
最終ジャッジ日時 2025-04-24 12:21:10
合計ジャッジ時間 5,605 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

internal_max_deficit = [0] * (n + 1)
internal_balance = [0] * (n + 1)

current_balance = 0
max_deficit = 0

for i in range(1, n + 1):
    char = s[i - 1]
    if char == '(':
        current_balance += 1
    else:
        current_balance -= 1
    max_deficit = max(max_deficit, -current_balance)
    internal_max_deficit[i] = max_deficit
    internal_balance[i] = current_balance

pre_order = []
for i in range(1, n + 1):
    bal = internal_balance[i]
    if bal >= 0:
        r_i = (i - bal) // 2
        l_i = (i + bal) // 2
        key = (0, r_i, -l_i)
    else:
        l_i = (i + bal) // 2
        r_i = (i - bal) // 2
        key = (1, -l_i, r_i)
    pre_order.append((key, i))

pre_order.sort()
sorted_indices = [i for (key, i) in pre_order]

current_balance_sim = 0
global_max_deficit = 0

for i in sorted_indices:
    D_i = internal_max_deficit[i]
    bal_i = internal_balance[i]
    contribution = D_i - current_balance_sim
    if contribution > global_max_deficit:
        global_max_deficit = contribution
    current_balance_sim += bal_i

sum_balance = sum(internal_balance[1:n+1])
total = n * (n + 1) // 2
total_left = (total + sum_balance) // 2
total_right = (total - sum_balance) // 2

min_lr = min(total_left, total_right)
answer = max(0, 2 * min_lr - 2 * global_max_deficit)

print(answer)
0