結果
問題 |
No.684 Prefix Parenthesis
|
ユーザー |
![]() |
提出日時 | 2025-04-15 23:02:17 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,471 bytes |
コンパイル時間 | 155 ms |
コンパイル使用メモリ | 82,320 KB |
実行使用メモリ | 96,696 KB |
最終ジャッジ日時 | 2025-04-15 23:04:06 |
合計ジャッジ時間 | 3,781 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 3 TLE * 1 -- * 27 |
ソースコード
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()