codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.