2107C.md (3401B)
1 Source: https://codeforces.com/problemset/problem/2107/C 2 3 C. Maximum Subarray Sum 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given an array $a_1,a_2,\ldots,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. 22 23 Formally, you are given a binary string $s$ and a partially filled array $a$, where: 24 25 * If you remember the value of $a_i$, $s_i = 1$ to indicate that, and you are given the real value of $a_i$. 26 * If you don't remember the value of $a_i$, $s_i = 0$ to indicate that, and you are given $a_i = 0$. 27 28 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}$. 29 30 $^{\text{∗}}$The maximum subarray sum of an array $a$ of length $n$, i.e. $a_1, a_2, \ldots 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} + \ldots + a_j$. 31 32 Input 33 34 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. 35 36 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}$). 37 38 The second line of each test case contains a binary ($\texttt{01}$) string $s$ of length $n$. 39 40 The third line of each test case contains $n$ numbers $a_1,a_2,\ldots,a_n$ ($|a_i| \le 10^6$). If $s_i = \texttt{0}$, then it's guaranteed that $a_i = 0$. 41 42 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 43 44 Output 45 46 For each test case, first output $\texttt{Yes}$ if a solution exists or $\texttt{No}$ if no solution exists. You may print each character in either case, for example $\texttt{YES}$ and $\texttt{yEs}$ will also be accepted. 47 48 If there's at least one solution, print $n$ numbers $a_1,a_2,\ldots,a_n$ on the second line. $|a_i| \le 10^{18}$ must hold. 49 50 Example 51 52 Input 53 54 ``` 55 10 56 57 3 5 58 59 011 60 61 0 0 1 62 63 5 6 64 65 11011 66 67 4 -3 0 -2 1 68 69 4 4 70 71 0011 72 73 0 0 -4 -5 74 75 6 12 76 77 110111 78 79 1 2 0 5 -1 9 80 81 5 19 82 83 00000 84 85 0 0 0 0 0 86 87 5 19 88 89 11001 90 91 -8 6 0 0 -5 92 93 5 10 94 95 10101 96 97 10 0 10 0 10 98 99 1 1 100 101 1 102 103 0 104 105 3 5 106 107 111 108 109 3 -1 3 110 111 4 5 112 113 1011 114 115 -2 0 1 -5 116 ``` 117 118 Output 119 120 ``` 121 Yes 122 4 0 1 123 Yes 124 4 -3 5 -2 1 125 Yes 126 2 2 -4 -5 127 No 128 Yes 129 5 1 9 2 2 130 Yes 131 -8 6 6 7 -5 132 Yes 133 10 -20 10 -20 10 134 No 135 Yes 136 3 -1 3 137 Yes 138 -2 4 1 -5 139 ``` 140 141 Note 142 143 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$. 144 145 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. 146 147 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]$. 148 149 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.