← 返回题目列表

Codeforces · 2179/E

E. Blackslex 和女孩

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

在使用 De Bruijn 固定长度比特串序列未能找到一个女孩后,Blackslex 将注意力转向了政治。

由于他的高魅力,他现在负责为他的国家的 $$$n$$$ 选区划定边界。在Blackslex的国家里,A党有$$$x$$$选民,B党有$$$y$$$选民。利用他惊人的绘画技巧,他可以将任何政党的选民分配到他选择的任何选区。

他的比特串历史让他想知道是否可以分配选民,使每个选区的获胜者遵循某种比特串模式。为了避免怀疑,他还必须将至少 $$$p_i$$$ 选民分配到每个选区。告诉他是否可以!

正式地,您将获得一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$、一个长度为 $$$n$$$ 的数组 $$$p$$$ 以及两个整数 $$$x$$$ 和 $$$y$$$。

您想要确定是否存在两个长度为 $$$n$$$ 的非负整数数组 $$$a$$$ 和 $$$b$$$ 满足以下条件:

  • $$$a_1 + a_2 + \dots + a_n = x$$$
  • $$$b_1 + b_2 + \dots + b_n = y$$$
  • 对于每个 $$$1 \leq i \leq n$$$,$$$a_i + b_i \geq p_i$$$
  • 对于每个 $$$1 \leq i \leq n$$$:
    • 如果 $$$s_i = 0$$$ 则 $$$a_i \gt b_i$$$
    • 如果 $$$s_i = 1$$$ 则 $$$b_i \gt a_i$$$

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$x$$$ 和 $$$y$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$、$$$1 \leq x, y \leq 10^9$$$)。

第二行包含长度为 $$$n$$$ 的二进制字符串 $$$s$$$。

第三行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ ($$$1 \leq p_i \leq 10^9$$$)。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印(不区分大小写) 是 如果存在满足所有条件的数组 $$$a, b$$$,或者 NO 否则。

示例

输入
复制

6
3 5 5
010
2 4 3
4 2 3
0001
1 1 1 1
2 4 2
00
3 3
4 23 20
1111
2 2 2 2
1 25 26
0
51
2 4 2
00
3 4

输出
复制

YES
NO
YES
NO
NO
NO

注意

在第一个测试用例中,选民的可能分布之一是:$$$a = [2, 0, 3]$$$ 和 $$$b = [0, 4, 1]$$$。

在第三个测试用例中,选民的可能分布之一是:$$$a = [2, 2]$$$ 和 $$$b = [1, 1]$$$。

对于其他测试用例,可以证明不存在满足条件的选民分布。