当前没有测试数据。

C. Maximum Subarray Sum

题目描述

给定一个长度为 $n$ 的数组 $a_1, a_2, \ldots, a_n$ 和一个正整数 $k$，但数组 $a$ 的某些部分缺失。你的任务是填充缺失的部分，使得数组 $a$ 的最大子数组和恰好等于 $k$，或者报告无解。

形式上，给定一个二进制字符串 $s$ 和一个部分填充的数组 $a$，其中：

• 若 $s_i = 1$，表示你记得 $a_i$ 的值，此时给定 $a_i$ 的真实值；
• 若 $s_i = 0$，表示你不记得 $a_i$ 的值，此时给定 $a_i = 0$（仅为占位符）。

所有你记得的值满足 $|a_i| \le 10^6$。你可以用绝对值不超过 $10^{18}$ 的任意整数填充缺失的值。可以证明，若存在解，则一定存在满足 $|a_i| \le 10^{18}$ 的解。

注：数组 $a$ 的最大子数组和定义为 $\max_{1 \le i \le j \le n} S(i, j)$，其中 $S(i, j) = a_i + a_{i+1} + \ldots + a_j$。

输入格式

第一行包含测试用例数 $t$（$1 \le t \le 10^4$）。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \cdot 10^5$，$1 \le k \le 10^{12}$）。 第二行包含一个长度为 $n$ 的二进制字符串 $s$。 第三行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$|a_i| \le 10^6$）。若 $s_i = 0$，则保证 $a_i = 0$。

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

输出格式

对于每个测试用例：

• 若存在解，输出 "Yes"，并在下一行输出填充后的数组 $a_1, a_2, \ldots, a_n$（$|a_i| \le 10^{18}$）；
• 若无解，输出 "No"。

输出字符串不区分大小写（如 "YES"、"yEs" 均合法）。

样例输入

10
3 5
011
0 0 1
5 6
11011
4 -3 0 -2 1
4 4
0011
0 0 -4 -5
6 12
110111
1 2 0 5 -1 9
5 19
00000
0 0 0 0 0
5 19
11001
-8 6 0 0 -5
5 10
10101
10 0 10 0 10
1 1
1
0
3 5
111
3 -1 3
4 5
1011
-2 0 1 -5

样例输出

Yes
4 0 1
Yes
4 -3 5 -2 1
Yes
2 2 -4 -5
No
Yes
5 1 9 2 2
Yes
-8 6 6 7 -5
Yes
10 -20 10 -20 10
No
Yes
3 -1 3
Yes
-2 4 1 -5

样例解释

• 测试用例1：仅第一个位置缺失，填充4后数组为[4, 0, 1]，最大子数组和为5。
• 测试用例2：仅第三个位置缺失，填充5后数组为[4, -3, 5, -2, 1]，最大子数组和来自[4, -3, 5]，和为6。
• 测试用例3：第一、二位缺失，填充2后数组为[2, 2, -4, -5]，最大子数组和为4（其他填充方式如[0, 4, -4, -5]也合法）。
• 测试用例4：无解。例如填充0后数组为[1, 2, 0, 5, -1, 9]，最大子数组和为16≠12。