Score : $300$ points

问题描述

设有 $N$ 个人，每个人要么是儿童要么是成年人。第 $i$ 个人的体重为 $W_i$。

每个人是儿童还是成年人的信息由一个长度为 $N$ 的字符串 $S$ 给出，该字符串仅包含字符 0 和 1。如果字符串 $S$ 的第 $i$ 个字符为 0，则表示第 $i$ 个人是儿童；若为 1，则表示第 $i$ 个人是成年人。

当给机器人高桥一个实数 $X$ 时，高桥会按照以下规则判断：体重小于 $X$ 的人被判断为儿童，体重大于等于 $X$ 的人被判断为成年人。

对于一个实数值 $X$，令 $f(X)$ 表示高桥正确判断儿童或成年人人数的数量。

找出所有实数 $X$ 中，$f(X)$ 的最大值。

以上为通义千问 qwen-max 翻译，仅供参考。

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.

update @ 2024/3/10 10:55:14