結果
問題 |
No.2591 安上がりな括弧列
|
ユーザー |
|
提出日時 | 2025-07-21 08:53:46 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 849 bytes |
コンパイル時間 | 388 ms |
コンパイル使用メモリ | 82,608 KB |
実行使用メモリ | 108,488 KB |
最終ジャッジ日時 | 2025-07-21 08:53:50 |
合計ジャッジ時間 | 4,305 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 8 WA * 15 |
ソースコード
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)] dp[1][0] = 0 if S[1]=="(": dp[1][0] = A[1] dp[1][1] = 0 if S[1]==")": dp[1][1] = A[1] for i in range(2,2*N+1): for j in range(i+1): if j==0: if S[i]==")": dp[i][0] = min(dp[i-1][1],dp[i-1][0]) else: dp[i][0] = min(dp[i-1][0],dp[i-1][1])+A[i] elif j==i: if S[i]=="(": dp[i][i] = dp[i-1][i-1] else: dp[i][i] = dp[i-1][i-1]+A[i] else: a = dp[i-1][j-1] if S[i]==")": a += A[i] b = dp[i-1][j+1] if S[i]=="(": b += A[i] dp[i][j] = min(a,b) print(dp[2*N][0])