题目描述

在尝试用定长比特串的 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 > b_i$
  • 如果 $s_i = 1$，则 $b_i > a_i$

输入格式

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

每个测试用例的第一行包含三个整数 $n$、$x$ 和 $y$（$1 \leq n \leq 2 \times 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 \times 10^5$。

输出格式

对于每个测试用例，如果存在满足所有条件的数组 $a, b$，则输出（不区分大小写）YES，否则输出 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]$。

对于其他测试用例，可以证明不存在满足要求的分配方案。

由 ChatGPT 5 翻译

来源

Codeforces 2179E，英文题名 Blackslex and Girls。