Codeforces Round 1023 (Div. 2) C. Maximum Subarray Sum

Codeforces Round 1023 (Div. 2) C. Maximum Subarray Sum

题目

You are given an array $a_1,a_2,\dots ,a_n$ of length $n$ and a positive integer $k$, but some parts of the array $a$ are missing. Your task is to fill the missing part so that the maximum subarray sum${}^{\text{∗}}$ of $a$ is exactly $k$, or report that no solution exists.

Formally, you are given a binary string $s$ and a partially filled array $a$, where:

• If you remember the value of $a_i$, $s_i=1$ to indicate that, and you are given the real value of $a_i$.
• If you don’t remember the value of $a_i$, $s_i=0$ to indicate that, and you are given $a_i=0$.

All the values that you remember satisfy $|a_i|\le 10^6$. However, you may use values up to $10^{18}$ to fill in the values that you do not remember. It can be proven that if a solution exists, a solution also exists satisfying $|a_i|\le 10^{18}$.

${}^{\text{∗}}$The maximum subarray sum of an array $a$ of length $n$, i.e. $a_1,a_2,\dots a_n$ is defined as ${\max }_{1\le i\le j\le n}S(i,j)$ where $S(i,j)=a_i+a_{i+1}+\dots +a_j$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 10^4$). The description of the test cases follows.

The first line of each test case contains two numbers $n,k$ ($1\le n\le 2\cdot 10^5,1\le k\le 10^{12}$).

The second line of each test case contains a binary ($\text{01}$) string $s$ of length $n$.

The third line of each test case contains $n$ numbers $a_1,a_2,\dots ,a_n$ ($|a_i|\le 10^6$). If $s_i=\text{0}$, then it’s guaranteed that $a_i=0$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, first output $\text{Yes}$ if a solution exists or $\text{No}$ if no solution exists. You may print each character in either case, for example $\text{YES}$ and $\text{yEs}$ will also be accepted.

If there’s at least one solution, print $n$ numbers $a_1,a_2,\dots ,a_n$ on the second line. $|a_i|\le 10^{18}$ must hold.

Example

Input

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

Output

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

Note

In test case $1$, only the first position is not filled. We can fill it with $4$ to get the array $[4,0,1]$ which has maximum subarray sum of $5$.

In test case $2$, only the third position is not filled. We can fill it with $5$ to get the array $[4,-3,5,-2,1]$. Here the maximum subarray sum comes from the subarray $[4,-3,5]$ and it is $6$, as required.

In test case $3$, the first and second positions are unfilled. We can fill both with $2$ to get the array $[2,2,-4,-5]$ which has a maximum subarray sum of $4$. Note that other outputs are also possible such as $[0,4,-4,-5]$.

In test case $4$, it is impossible to get a valid array. For example, if we filled the third position with $0$, we get $[1,2,0,5,-1,9]$, but this has a maximum subarray sum of $16$, not $12$ as required.

题目解析及思路

题目要求判断未确定的数组是否能使其最大子数组和恰好=k

对于二进制串s，如果s_i = 0，则说明a_i可以调整

首先考虑把所有不确定值全部赋成-INF，求一遍最大子数组和，如果已经>k 说明没有构造方案，否则实际只需要考虑一个不确定位置即可(其他依旧-INF)

因为可以调到很大值，使最大子数组和=k

代码

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;void solve(){int n,k;string s;cin>>n>>k>>s;vector<int> a(n);for(int &x:a) cin>>x;int pos = -1;int mx = 0,cur = 0;for(int i=0;i<n;i++){if(s[i] == '0'){//只留最后一个就可以了pos = i;a[i] = -1e13;}}for(int i=0;i<n;i++){cur = max(cur+a[i],a[i]);mx = max(mx,cur);}//如果已经>k或者不为k但是没有不确定的位置//都没有构造方案if(mx > k || (mx != k && pos == -1)){cout<<"NO"<<endl;return;}if(pos != -1){mx = 0,cur = 0;//对于提前找到的不确定位置//求他两边的最大子数组和for(int i=pos+1;i<n;i++){cur += a[i];mx = max(mx,cur);}//左边最大和int l = mx;mx = 0,cur = 0;for(int i=pos-1;i>=0;i--){cur += a[i];mx = max(mx,cur);}//右边最大和int r = mx;//构造的值a[pos] = k - l - r;}cout<<"YES"<<endl;for(int i=0;i<n;i++){cout<<a[i]<<" ";}cout<<endl;}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--){solve();}
}