結果

問題 No.684 Prefix Parenthesis
コンテスト
ユーザー lam6er
提出日時 2025-04-15 23:06:54
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,471 bytes
コンパイル時間 198 ms
コンパイル使用メモリ 82,468 KB
実行使用メモリ 97,688 KB
最終ジャッジ日時 2025-04-15 23:09:04
合計ジャッジ時間 3,754 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    n = int(sys.stdin.readline())
    s = sys.stdin.readline().strip()
    
    a = [0] * (n + 1)  # a[i] is the number of '(' in S_i
    b = [0] * (n + 1)  # b[i] is the number of ')' in S_i
    bal = [0] * (n + 1)  # balance after processing S_i
    min_bal = [0] * (n + 1)  # minimum balance in S_i
    pairs = [0] * (n + 1)  # pairs in S_i when processed with initial balance 0
    
    current_balance = 0
    current_min = 0
    current_pairs = 0
    current_open = 0
    
    for i in range(1, n + 1):
        c = s[i-1]
        a[i] = a[i-1] + (c == '(')
        b[i] = b[i-1] + (c == ')')
        current_balance = a[i] - b[i]
        if c == '(':
            current_open += 1
        else:
            if current_open > 0:
                current_open -= 1
                current_pairs += 1
        pairs[i] = current_pairs
        # Compute min_bal[i]
        if i == 1:
            min_bal[i] = current_balance
        else:
            min_bal[i] = min(min_bal[i-1], current_balance)
        bal[i] = current_balance
    
    # Prepare list of tuples (min_bal_i, bal_i, a_i, b_i, pairs_i)
    # We need to sort the indices 1..n
    indices = list(range(1, n+1))
    
    # Custom comparator based on min_bal and bal
    def compare(i, j):
        # Compare i and j based on the combined min_bal
        val_i = min(min_bal[i], bal[i] + min_bal[j])
        val_j = min(min_bal[j], bal[j] + min_bal[i])
        if val_i > val_j:
            return -1
        elif val_i < val_j:
            return 1
        else:
            return 0
    
    # Sort using the comparator
    from functools import cmp_to_key
    indices.sort(key=cmp_to_key(compare))
    
    # Now simulate processing the sorted indices
    total_pairs = 0
    current_open = 0
    
    for idx in indices:
        # Process S_idx's characters with current_open
        # We need to compute how many pairs are added
        # and update current_open
        # To do this, we need to process each character in S_idx
        # which is the first idx characters of s
        temp_open = current_open
        temp_pairs = 0
        for c in s[:idx]:
            if c == '(':
                temp_open += 1
            else:
                if temp_open > 0:
                    temp_open -= 1
                    temp_pairs += 1
        total_pairs += temp_pairs
        current_open = temp_open
    
    print(2 * total_pairs)
    
if __name__ == "__main__":
    main()
0