codeforces-scrape

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

1743C.md (2677B)


      1 Source: https://codeforces.com/problemset/problem/1743/C
      2 
      3 C. Save the Magazines
      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 Monocarp has been collecting rare magazines for quite a while, and now he has decided to sell them. He distributed the magazines between $n$ boxes, arranged in a row. The $i$-th box contains $a_i$ magazines. Some of the boxes are covered with lids, others are not.
     22 
     23 Suddenly it started to rain, and now Monocarp has to save as many magazines from the rain as possible. To do this, he can move the lids between boxes as follows: if the $i$-th box was covered with a lid initially, he can either move the lid from the $i$-th box to the box $(i-1)$ (if it exists), or keep the lid on the $i$-th box. You may assume that Monocarp can move the lids instantly at the same moment, and no lid can be moved more than once. If a box will be covered with a lid after Monocarp moves the lids, the magazines in it will be safe from the rain; otherwise they will soak.
     24 
     25 You have to calculate the maximum number of magazines Monocarp can save from the rain.
     26 
     27 Input
     28 
     29 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of the testcases.
     30 
     31 The first line of each testcase contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of boxes.
     32 
     33 The second line contains a string of $n$ characters 0 and/or 1. If the $i$-th character is 1, the $i$-th box is initially covered with a lid. If the $i$-th character is 0, the $i$-th box is initially not covered.
     34 
     35 The third line contains a sequence of integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^4$), where $a_i$ is the number of magazines in the $i$-th box.
     36 
     37 The sum of $n$ over all testcases doesn't exceed $2 \cdot 10^5$.
     38 
     39 Output
     40 
     41 For each testcase, print one integer — the maximum number of magazines Monocarp can save from the rain.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 4
     49 
     50 5
     51 
     52 01110
     53 
     54 10 5 8 9 6
     55 
     56 6
     57 
     58 011011
     59 
     60 20 10 9 30 20 19
     61 
     62 4
     63 
     64 0000
     65 
     66 100 100 100 100
     67 
     68 4
     69 
     70 0111
     71 
     72 5 4 5 1
     73 ```
     74 
     75 Output
     76 
     77 ```
     78 27
     79 80
     80 0
     81 14
     82 ```
     83 
     84 Note
     85 
     86 In the first testcase of the example, Monocarp can move the lid from the second box to the first box, so the boxes $1$, $3$ and $4$ are covered, and $10 + 8 + 9 = 27$ magazines are saved.
     87 
     88 In the second testcase, Monocarp can move the lid from the second box to the first box, then from the third box to the second box, then from the fifth box to the fourth box, and then from the sixth box to the fifth box. The boxes $1$, $2$, $4$ and $5$ will be covered, so $20 + 10 + 30 + 20 = 80$ magazines can be saved.
     89 
     90 There are no lids in the third testcase, so it's impossible to save even a single magazine.