結果

問題 No.3147 Parentheses Modification and Rotation (RM Ver.)
ユーザー SPD_9X2
提出日時 2025-05-16 22:49:41
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 75 ms / 2,000 ms
コード長 805 bytes
コンパイル時間 270 ms
コンパイル使用メモリ 82,512 KB
実行使用メモリ 83,520 KB
最終ジャッジ日時 2025-05-16 22:49:46
合計ジャッジ時間 3,449 ms
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #


import sys

N = int(input())
S = input()
R,M = map(int,input().split())

if N % 2 == 1:
    print (-1)
    sys.exit()

h = []
nowh = 0
for c in S:
    if c == "(":
        nowh += 1
    else:
        nowh -= 1
    h.append(nowh)

lmin = [i for i in h]
for i in range(N-1):
    lmin[i+1] = min(lmin[i+1], lmin[i])

rmin = [i for i in h]
for i in range(N-1,0,-1):
    rmin[i-1] = min(rmin[i-1], rmin[i])

ans = float("inf")
for fi in range(N):

    move = 0 if fi==0 else (N-fi)*R


    baseh = 0 if fi==0 else h[fi-1]

    RR = rmin[fi]-baseh
    LL = 0 if fi==0 else (h[-1]-baseh) + lmin[fi-1]
    nmin = min(LL,RR)

    mov = (abs(nmin)+1) // 2
    nsum = nowh + 2*mov

    add_cost = ( abs(mov) + abs(nsum)//2 ) * M

    # print ( fi, move, add_cost )
    ans = min(ans, move + add_cost)

print (ans)
0