102572: [AtCoder]ABC257 C - Robot Takahashi

Problem Statement

There are $N$ people, each of whom is either a child or an adult. The $i$-th person has a weight of $W_i$.
Whether each person is a child or an adult is specified by a string $S$ of length $N$ consisting of 0 and 1.
If the $i$-th character of $S$ is 0, then the $i$-th person is a child; if it is 1, then the $i$-th person is an adult.

When Takahashi the robot is given a real number $X$, Takahashi judges a person with a weight less than $X$ to be a child and a person with a weight more than or equal to $X$ to be an adult.
For a real value $X$, let $f(X)$ be the number of people whom Takahashi correctly judges whether they are children or adults.

Find the maximum value of $f(X)$ for all real values of $X$.

Constraints

• $1\leq N\leq 2\times 10^5$
• $S$ is a string of length $N$ consisting of 0 and 1.
• $1\leq W_i\leq 10^9$
• $N$ and $W_i$ are integers.

Input

Input is given from Standard Input in the following format:

$N$
$S$
$W_1$ $W_2$ $\ldots$ $W_N$

Output

Print the maximum value of $f(X)$ as an integer in a single line.

Sample Input 1

5
10101
60 45 30 40 80

Sample Output 1

4

When Takahashi is given $X=50$, it judges the $2$-nd, $3$-rd, and $4$-th people to be children and the $1$-st and $5$-th to be adults.
In reality, the $2$-nd and $4$-th are children, and the $1$-st, $3$-rd, and $5$-th are adults, so the $1$-st, $2$-nd, $4$-th, and $5$-th people are correctly judged. Thus, $f(50)=4$.

This is the maximum since there is no $X$ that judges correctly for all $5$ people. Thus, $4$ should be printed.

Sample Input 2

3
000
1 2 3

Sample Output 2

3

For example, $X=10$ achieves the maximum value $f(10)=3$.
Note that the people may be all children or all adults.

Sample Input 3

5
10101
60 50 50 50 60

Sample Output 3

4

For example, $X=55$ achieves the maximum value $f(55)=4$.
Note that there may be multiple people with the same weight.

问题描述

有$N$个人，他们每个人要么是儿童，要么是成人。第$i$个人的体重为$W_i$。
每个人是儿童还是成人的信息由一个长度为$N$的字符串$S$给出，字符串由0和1组成。
如果字符串$S$的第$i$个字符为0，则第$i$个人是儿童；如果为1，则第$i$个人是成人。

当机器人Takahashi被赋予一个实数$X$时，
Takahashi会将体重小于$X$的人判断为儿童，将体重大于等于$X$的人判断为成人。
对于一个实数$X$，令$f(X)$为Takahashi正确判断出儿童和成人的人数。

求对于所有实数$X$，$f(X)$的最大值。

约束

• $1\leq N\leq 2\times 10^5$
• $S$是一个长度为$N$的字符串，由0和1组成。
• $1\leq W_i\leq 10^9$
• $N$和$W_i$是整数。

输入

从标准输入以如下格式给出输入：

$N$
$S$
$W_1$ $W_2$ $\ldots$ $W_N$

输出

在一行中打印出$f(X)$的最大值作为整数。

样例输入1

5
10101
60 45 30 40 80

样例输出1

4

当Takahashi被赋予$X=50$时，它会将第$2$、$3$、$4$个人判断为儿童，将第$1$、$5$个人判断为成人。
实际上，第$2$、$4$个人是儿童，第$1$、$3$、$5$个人是成人，所以第$1$、$2$、$4$、$5$个人被正确判断出。
因此，$f(50)=4$。

由于没有$X$能够将这$5$个人全部正确判断，因此应打印出$4$。

样例输入2

3
000
1 2 3

样例输出2

3

例如，$X=10$时，$f(10)=3$。
注意，这些人可能都是儿童或都是成人。

样例输入3

5
10101
60 50 50 50 60

样例输出3

4

例如，$X=55$时，$f(55)=4$。
注意，可能存在多个体重相同的人。