結果

問題 No.2591 安上がりな括弧列
コンテスト
ユーザー LyricalMaestro
提出日時 2024-12-30 02:59:08
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 129 ms / 2,000 ms
コード長 938 bytes
コンパイル時間 206 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 76,672 KB
最終ジャッジ日時 2024-12-30 02:59:11
合計ジャッジ時間 3,152 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/2591

MAX_VALUE = 10 ** 18

def main():
    N = int(input())
    S = input()
    A = list(map(int, input().split()))

    dp = [MAX_VALUE] * (2 * N + 1)
    dp[0] = 0
    for i in range(2 * N):
        s = S[i]
        a = A[i]

        new_dp = [MAX_VALUE] * (2 * N + 1)

        if s == "(":
            for d in range(2 * N + 1):
                if d + 1 <= 2 * N:
                    new_dp[d + 1] = min(new_dp[d + 1], dp[d])
                
                if d - 1 >= 0:
                    new_dp[d - 1] = min(new_dp[d - 1], dp[d] + a)
        else:
            for d in range(2 * N + 1):
                if d + 1 <= 2 * N:
                    new_dp[d + 1] = min(new_dp[d + 1], dp[d] + a)
                
                if d - 1 >= 0:
                    new_dp[d - 1] = min(new_dp[d - 1], dp[d])
        dp = new_dp
    
    print(dp[0])




    






if __name__ == '__main__':
    main()
0