codeforces-scrape

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

2070C.md (2678B)


      1 Source: https://codeforces.com/problemset/problem/2070/C
      2 
      3 C. Limited Repainting
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given a strip, consisting of $n$ cells, all cells are initially colored red.
     22 
     23 In one operation, you can choose a segment of consecutive cells and paint them blue. Before painting, the chosen cells can be either red or blue. Note that it is not possible to paint them red. You are allowed to perform at most $k$ operations (possibly zero).
     24 
     25 For each cell, the desired color after all operations is specified: red or blue.
     26 
     27 It is clear that it is not always possible to satisfy all requirements within $k$ operations. Therefore, for each cell, a penalty is also specified, which is applied if the cell ends up the wrong color after all operations. For the $i$-th cell, the penalty is equal to $a_i$.
     28 
     29 The penalty of the final painting is calculated as the maximum penalty among all cells that are painted the wrong color. If there are no such cells, the painting penalty is equal to $0$.
     30 
     31 What is the minimum penalty of the final painting that can be achieved?
     32 
     33 Input
     34 
     35 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     36 
     37 The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 3 \cdot 10^5$; $0 \le k \le n$) — the length of the strip and the maximum number of operations.
     38 
     39 The second line contains a string $s$, consisting of $n$ characters 'R' and/or 'B'. 'R' means that the cell should be painted red. 'B' means that the cell should be painted blue.
     40 
     41 The third line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the penalty for each cell.
     42 
     43 The sum of $n$ over all test cases does not exceed $3 \cdot 10^5$.
     44 
     45 Output
     46 
     47 For each test case, print a single integer — the minimum penalty of the final painting.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 5
     55 
     56 4 1
     57 
     58 BRBR
     59 
     60 9 3 5 4
     61 
     62 4 1
     63 
     64 BRBR
     65 
     66 9 5 3 4
     67 
     68 4 2
     69 
     70 BRBR
     71 
     72 9 3 5 4
     73 
     74 10 2
     75 
     76 BRBRBBRRBR
     77 
     78 5 1 2 4 5 3 6 1 5 4
     79 
     80 5 5
     81 
     82 RRRRR
     83 
     84 5 3 1 2 4
     85 ```
     86 
     87 Output
     88 
     89 ```
     90 3
     91 3
     92 0
     93 4
     94 0
     95 ```
     96 
     97 Note
     98 
     99 In the first test case, you can paint the cells from $1$ to $3$. The painting will be BBBR. So, only cell $2$ is painted the wrong color. Therefore, the penalty for it is the final penalty and equals $3$.
    100 
    101 In the second test case, the painting BBBR will now result in a penalty of $5$. However, if you paint the cells from $1$ to $1$, resulting in BRRR, then only cell $3$ is painted the wrong color. The final penalty is $3$.
    102 
    103 In the third test case, you can paint the cells from $1$ to $1$ and from $3$ to $3$. Then all cells will be the correct color, the penalty equals $0$.