結果

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

ソースコード

diff # 

def main():
    import sys
    n = int(sys.stdin.readline())
    s = sys.stdin.readline().strip()
    
    prefixes = []
    total_left = 0
    total_right = 0
    for i in range(n):
        current = s[:i+1]
        a = current.count('(')
        b = current.count(')')
        total_left += a
        total_right += b
        balance = 0
        min_balance = 0
        for c in current:
            if c == '(':
                balance += 1
            else:
                balance -= 1
            if balance < min_balance:
                min_balance = balance
        prefixes.append((a, b, balance, min_balance))
    
    pos = []
    neg = []
    for p in prefixes:
        a, b, bal, min_bal = p
        if bal >= 0:
            pos.append(p)
        else:
            neg.append(p)
    
    pos.sort(key=lambda x: x[3])
    neg.sort(key=lambda x: -(x[2] - x[3]))
    
    ordered = pos + neg
    
    max_pairs = 0
    current_balance = 0
    for a, b, bal, min_bal in ordered:
        for c in s[:a + b]:
            if c == '(':
                current_balance += 1
            else:
                if current_balance > 0:
                    current_balance -= 1
                    max_pairs += 1
    
    print(2 * max_pairs)
    
if __name__ == "__main__":
    main()
0