分数: 300 点
问题陈述
有 N 人,每个人都是儿童或成人。 的 i- 第一个人的体重为 W_i.
通过字符串指定每个人是儿童还是成人 S 长度 N 组成 0 和 1.
如果 i- 第一个字符 S is 0,然后 i第一个人是一个孩子;如果是的话 1,然后 i第一个人是成年人。
当高桥给机器人一个实数时 X,
高桥判断体重小于 X 儿童和体重大于或等于 X 成为成年人。
对于实际值 X,让 f(X) 是高桥正确判断是儿童还是成人的人数。
找到最大值 f(X) 对于所有实际值 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
当高桥给出时 X=50,它判断 2-nd, 3-rd,和 4第一个孩子和 1-st 和 5- 即将成为成年人。
实际上, 2-nd 和 4-th 是孩子,并且 1-st, 3-rd,和 5-th 是成年人,所以 1-st, 2-nd, 4-th,以及 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.
请注意,可能有多个人具有相同的体重。