結果
問題 |
No.2591 安上がりな括弧列
|
ユーザー |
|
提出日時 | 2025-07-21 09:52:06 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 152 ms / 2,000 ms |
コード長 | 692 bytes |
コンパイル時間 | 431 ms |
コンパイル使用メモリ | 82,772 KB |
実行使用メモリ | 108,232 KB |
最終ジャッジ日時 | 2025-07-21 09:52:11 |
合計ジャッジ時間 | 3,758 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
N = int(input()) S = "0"+input().strip() A = [0]+list(map(int,input().split())) INFTY = 10**12+100 dp = [[INFTY for _ in range(2*N+1)] for _ in range(2*N+1)] if S[1]=="(": dp[1][1] = 0 else: dp[1][1] = A[1] for i in range(2,2*N+1): for j in range(i+1): if j==0: dp[i][0] = dp[i-1][1] if S[i]=="(": dp[i][0] += A[i] elif j==i: dp[i][i] = dp[i-1][i-1] if S[i]==")": dp[i][i] += A[i] else: if S[i]=="(": dp[i][j] = min(dp[i-1][j-1], dp[i-1][j+1]+A[i]) else: dp[i][j] = min(dp[i-1][j+1], dp[i-1][j-1]+A[i]) print(dp[2*N][0])