結果

問題 No.684 Prefix Parenthesis
コンテスト
ユーザー tktk_snsn
提出日時 2021-01-16 09:28:00
言語 PyPy3
(7.3.17)
結果
WA  
実行時間 -
コード長 556 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 302 ms
コンパイル使用メモリ 82,124 KB
実行使用メモリ 88,244 KB
最終ジャッジ日時 2024-11-27 09:12:39
合計ジャッジ時間 4,761 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

N = int(input())
S = input()

R = 0  # (((
LR = []  # ))((
L = 0  # ))

ans = 0

add = 0
cntL = 0
cntR = 0
for s in S:
    if s == ")":
        if cntR:
            cntR -= 1
            add += 2
        else:
            cntL += 1
    elif s == "(":
        cntR += 1

    ans += add

    if cntL and cntR:
        LR.append((cntL, cntR))
    elif cntL:
        L += cntL
    elif cntR:
        R += cntR


LR.sort(key=lambda x: (x[0], -x[1]))
for l, r in LR:
    d = min(R, l)
    ans += 2 * d
    R -= d
    R += r
d = min(R, L)
ans += 2 * d

print(ans)
0