結果

問題 No.2591 安上がりな括弧列
ユーザー anonymouslyanonymously
提出日時 2023-12-19 17:03:41
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
TLE  
実行時間 -
コード長 1,135 bytes
コンパイル時間 170 ms
コンパイル使用メモリ 12,032 KB
実行使用メモリ 205,712 KB
最終ジャッジ日時 2023-12-19 17:03:46
合計ジャッジ時間 4,140 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 29 ms
17,044 KB
testcase_01 AC 28 ms
10,240 KB
testcase_02 AC 37 ms
10,496 KB
testcase_03 AC 29 ms
10,240 KB
testcase_04 AC 29 ms
10,240 KB
testcase_05 AC 28 ms
10,240 KB
testcase_06 AC 29 ms
10,240 KB
testcase_07 AC 29 ms
10,240 KB
testcase_08 AC 46 ms
12,032 KB
testcase_09 TLE -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

# coding: utf-8
import heapq

def isValid(S):
    a=0
    for c in S:
        if c=='(':
            a+=1
        elif c==')':
            a-=1
        else:
            raise Exception
        if a<0:
            return False
    return a==0    

def change(S,i):
    L=list(S)
    if S[i]=='(':
        L[i]=')'
    elif S[i]==')':
        L[i]='('
    else:
        raise Exception
    return "".join(L)

def dijkstra(n,S,A):
    closed=set()
    temp={}
    heap=[]
    heapq.heappush(heap,(0,S))
    while heap:
        tupl=heapq.heappop(heap)
        T=tupl[1]
        cost=tupl[0]
        if T not in closed:
            closed.add(T)
            if(isValid(T)):
                return cost
            for i in range(len(T)):
                U=change(T,i)
                if U not in closed:
                    if U not in temp:
                        temp[U]=cost+A[i]
                    else:
                        temp[U]=min(temp[U],cost+A[i])
                    heapq.heappush(heap,(temp[U],U))
    raise Exception

if __name__ == "__main__":
    print(dijkstra(int(input()),input(),list(map(int,input().split()))))
0