/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
0, 1 からなる長さ N の文字列 S が与えられます。
0, 1 からなる長さ N の文字列 T は以下の条件を満たすとき、またそのときに限り 良い文字列 であると定義します。
- 1 \leq i \leq N - 1 を満たす整数 i であって、T の i 文字目と i + 1 文字目が一致するようなものがちょうど 1 つ存在する。
i = 1,2,\ldots, N について以下の操作を 1 度行うか行わないか選ぶことができます。
- S の i 文字目が
0であるとき S の i 文字目を1に、そうでないとき S の i 文字目を0に置き換える。操作を行った場合、C_i のコストがかかる。
S を良い文字列にするために必要なコストの総和の最小値を求めてください。
制約
- 2 \leq N \leq 2 \times 10^5
- S は長さ N の
0,1からなる文字列 - 1 \leq C_i \leq 10^9
- N, C_i は整数
入力
入力は以下の形式で標準入力から与えられる。
N S C_1 C_2 \ldots C_N
出力
答えを出力せよ。
入力例 1
5 00011 3 9 2 6 4
出力例 1
7
i = 1, 5 に対して操作を行い、i = 2, 3, 4 に対して操作を行わないことで S = 10010 となり、S は良い文字列となります。このときかかるコストは 7 であり、コスト 7 未満で S を良い文字列にすることはできないため、7 を出力します。
入力例 2
4 1001 1 2 3 4
出力例 2
0
入力例 3
11 11111100111 512298012 821282085 543342199 868532399 690830957 973970164 928915367 954764623 923012648 540375785 925723427
出力例 3
2286846953
Score: 400 points
Problem Statement
You are given a string S of length N consisting of 0 and 1.
A string T of length N consisting of 0 and 1 is a good string if and only if it satisfies the following condition:
- There is exactly one integer i such that 1 \leq i \leq N - 1 and the i-th and (i + 1)-th characters of T are the same.
For each i = 1,2,\ldots, N, you can choose whether or not to perform the following operation once:
- If the i-th character of S is
0, replace it with1, and vice versa. The cost of this operation, if performed, is C_i.
Find the minimum total cost required to make S a good string.
Constraints
- 2 \leq N \leq 2 \times 10^5
- S is a string of length N consisting of
0and1. - 1 \leq C_i \leq 10^9
- N and C_i are integers.
Input
The input is given from Standard Input in the following format:
N S C_1 C_2 \ldots C_N
Output
Print the answer.
Sample Input 1
5 00011 3 9 2 6 4
Sample Output 1
7
Performing the operation for i = 1, 5 and not performing it for i = 2, 3, 4 makes S = 10010, which is a good string. The cost incurred in this case is 7, and it is impossible to make S a good string for less than 7, so print 7.
Sample Input 2
4 1001 1 2 3 4
Sample Output 2
0
Sample Input 3
11 11111100111 512298012 821282085 543342199 868532399 690830957 973970164 928915367 954764623 923012648 540375785 925723427
Sample Output 3
2286846953