/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
子供と大人があわせて N 人います。i 番目の人の体重は W_i です。
それぞれの人が子供か大人かは、0 と 1 からなる長さ N の文字列 S によって表され、
S の i 文字目が 0 であるとき i 番目の人が子供であることを、1 であるとき i 番目の人が大人であることをさします。
ロボットである高橋君に対して実数 X を設定すると、
高橋君はそれぞれの人に対して、体重が X 未満なら子供、X 以上なら大人と判定します。
実数 X に対してf(X) を、高橋君に X を設定したときに N 人のうち子供か大人かを正しく判定できる人数で定めます。
X が実数全体を動くとき、f(X) の最大値を求めてください。
制約
- 1\leq N\leq 2\times 10^5
- S は
0と1からなる長さ N の文字列 - 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
X=50 と設定すると、高橋君は 2,3,4 番目の人を子供、 1,5 番目の人を大人と判定します。
実際には 2,4 番目の人が子供、 1,3,5 番目の人が大人であるので、このとき、1,2,4,5 番目の合計 4 人に対して正しく判定できています。
よって、f(50)=4 です。
5 人全員に対して正しく判定できるような X は存在しないのでこのときが最大です。よって、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 を達成します。
同じ体重の人が複数人存在する可能性もあることに注意してください。
Score : 300 points
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
0and1. - 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.