← 返回题目列表

AtCoder · abc257_c

E. 机器人高桥

中文机器翻译题面 查看原题

分数: 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.
请注意,可能有多个人具有相同的体重。