/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 600 点
問題文
正整数 N、長さ N の # と . からなる文字列 S、長さ N の正整数列 R=(R_1,R_2,\dots,R_N) が与えられます。
N 個の区画が横 1 列に並んだ森林があります。区画には左から順に 1,2,\dots,N と番号が付けられています。
いくつかの区画には木が生えています。具体的には、S の i 文字目が # であるとき、またそのときに限り区画 i には木が生えています。ここで、次に示す操作を 1 回以上行うことができることが保証されます。
あなたは、以下の操作を好きなだけ繰り返すことができます。
- 木が生えていない区画を 2 つ選ぶ。選んだ区画を左から区画 i,j とすると、区画 i と区画 j の間にある木がすべてなくなり、R_i+R_j の報酬を得る。
ただし、木が 1 本もなくならないような操作を行うことはできません。
最終的に獲得できる報酬の総和の最大値を達成するために、最初に行うことのできる操作の数を求めてください。ただし、2 つの操作は、どちらか一方のみで選んでいる区画が存在するとき、またそのときに限り区別します。
制約
- 3\leq N\leq 2\times 10^5
- S の長さは N で、各文字は
#または. - 1\leq R_i\leq 10^9 (1\leq i\leq N)
- 操作を 1 回以上行うことができる
- N,R_i は整数
入力
入力は以下の形式で標準入力から与えられる。
N S R_1 R_2 \dots R_N
出力
答えを出力せよ。
入力例 1
8 ...###.. 20 25 1 1 30 2 1 1
出力例 1
2
最初に行うことのできる操作は以下の 6 通りです。
- 区画 1 と区画 7 を選ぶ。区画 4,5,6 にある木がなくなり、21 の報酬を得る。
- 区画 1 と区画 8 を選ぶ。区画 4,5,6 にある木がなくなり、21 の報酬を得る。
- 区画 2 と区画 7 を選ぶ。区画 4,5,6 にある木がなくなり、26 の報酬を得る。
- 区画 2 と区画 8 を選ぶ。区画 4,5,6 にある木がなくなり、26 の報酬を得る。
- 区画 3 と区画 7 を選ぶ。区画 4,5,6 にある木がなくなり、2 の報酬を得る。
- 区画 3 と区画 8 を選ぶ。区画 4,5,6 にある木がなくなり、2 の報酬を得る。
どの操作を行ったとしてもすべての木がなくなるので、2 回目の操作を行うことはできません。獲得できる報酬の総和の最大値は 26 です。
入力例 2
5 .#.#. 211 182 192 182 211
出力例 2
2
獲得できる報酬の総和の最大値は 825 です。
最初に得る報酬を最大化するのではないことに注意してください。最初に区画 1 と区画 5 を選ぶと 422 の報酬を獲得できますが、その後操作を行うことができず、報酬の総和を 825 にすることができません。
入力例 3
11 #..#.##.#.. 192 192 192 211 182 192 182 192 182 211 182
出力例 3
3
Score : 600 points
Problem Statement
You are given a positive integer N, a string S of length N consisting of # and ., and a length-N sequence of positive integers R=(R_1,R_2,\dots,R_N).
There is a forest with N sections arranged in a single horizontal line. The sections are numbered 1,2,\dots,N from left to right.
Some sections have trees. Specifically, section i has a tree if and only if the i-th character of S is #. It is guaranteed that the following operation can be performed at least once.
You can repeat the following operation as many times as you like:
- Choose two sections without trees. Let sections i and j (where i < j) be the chosen sections from left to right. Then, all trees between sections i and j are removed, and you gain a reward of R_i+R_j.
Here, you cannot perform an operation that removes no trees.
Find the number of ways to perform the first operation to achieve the maximum possible total reward. Two ways are considered distinct if and only if there exists a section chosen in one way but not in the other.
Constraints
- 3\leq N\leq 2\times 10^5
- The length of S is N, and each character is
#or.. - 1\leq R_i\leq 10^9 (1\leq i\leq N)
- The operation can be performed at least once.
- N and R_i are integers.
Input
The input is given from Standard Input in the following format:
N S R_1 R_2 \dots R_N
Output
Output the answer.
Sample Input 1
8 ...###.. 20 25 1 1 30 2 1 1
Sample Output 1
2
There are six ways to perform the first operation, as follows:
- Choose sections 1 and 7. The trees at sections 4,5,6 are removed, and you gain a reward of 21.
- Choose sections 1 and 8. The trees at sections 4,5,6 are removed, and you gain a reward of 21.
- Choose sections 2 and 7. The trees at sections 4,5,6 are removed, and you gain a reward of 26.
- Choose sections 2 and 8. The trees at sections 4,5,6 are removed, and you gain a reward of 26.
- Choose sections 3 and 7. The trees at sections 4,5,6 are removed, and you gain a reward of 2.
- Choose sections 3 and 8. The trees at sections 4,5,6 are removed, and you gain a reward of 2.
No matter which operation is performed, all trees are removed, so a second operation cannot be performed. The maximum possible total reward is 26.
Sample Input 2
5 .#.#. 211 182 192 182 211
Sample Output 2
2
The maximum possible total reward is 825.
Note that the goal is not to maximize the reward obtained in the first operation. If you choose sections 1 and 5 first, you can gain a reward of 422, but no operation can be performed afterwards, and the total reward cannot reach 825.
Sample Input 3
11 #..#.##.#.. 192 192 192 211 182 192 182 192 182 211 182
Sample Output 3
3