codeforces-scrape

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

2000D.md (2314B)


      1 Source: https://codeforces.com/problemset/problem/2000/D
      2 
      3 D. Right Left Wrong
      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 Vlad found a strip of $n$ cells, numbered from left to right from $1$ to $n$. In the $i$-th cell, there is a positive integer $a_i$ and a letter $s_i$, where all $s_i$ are either 'L' or 'R'.
     22 
     23 Vlad invites you to try to score the maximum possible points by performing any (possibly zero) number of operations.
     24 
     25 In one operation, you can choose two indices $l$ and $r$ ($1 \le l \lt r \le n$) such that $s_l$ = 'L' and $s_r$ = 'R' and do the following:
     26 
     27 * add $a_l + a_{l + 1} + \dots + a_{r - 1} + a_r$ points to the current score;
     28 * replace $s_i$ with '.' for all $l \le i \le r$, meaning you can no longer choose these indices.
     29 
     30 For example, consider the following strip:
     31 
     32 |  |  |  |  |  |  |
     33 | --- | --- | --- | --- | --- | --- |
     34 | $3$ | $5$ | $1$ | $4$ | $3$ | $2$ |
     35 | L | R | L | L | L | R |
     36 
     37 You can first choose $l = 1$, $r = 2$ and add $3 + 5 = 8$ to your score.
     38 
     39 |  |  |  |  |  |  |
     40 | --- | --- | --- | --- | --- | --- |
     41 | $3$ | $5$ | $1$ | $4$ | $3$ | $2$ |
     42 | . | . | L | L | L | R |
     43 
     44 Then choose $l = 3$, $r = 6$ and add $1 + 4 + 3 + 2 = 10$ to your score.
     45 
     46 |  |  |  |  |  |  |
     47 | --- | --- | --- | --- | --- | --- |
     48 | $3$ | $5$ | $1$ | $4$ | $3$ | $2$ |
     49 | . | . | . | . | . | . |
     50 
     51 As a result, it is impossible to perform another operation, and the final score is $18$.
     52 
     53 What is the maximum score that can be achieved?
     54 
     55 Input
     56 
     57 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     58 
     59 The first line of each test case contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the length of the strip.
     60 
     61 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$) — the numbers written on the strip.
     62 
     63 The third line of each test case contains a string $s$ of $n$ characters 'L' and 'R'.
     64 
     65 It is guaranteed that the sum of the values of $n$ across all test cases does not exceed $2 \cdot 10^5$.
     66 
     67 Output
     68 
     69 For each test case, output one integer — the maximum possible number of points that can be scored.
     70 
     71 Example
     72 
     73 Input
     74 
     75 ```
     76 4
     77 
     78 6
     79 
     80 3 5 1 4 3 2
     81 
     82 LRLLLR
     83 
     84 2
     85 
     86 2 8
     87 
     88 LR
     89 
     90 2
     91 
     92 3 9
     93 
     94 RL
     95 
     96 5
     97 
     98 1 2 3 4 5
     99 
    100 LRLRR
    101 ```
    102 
    103 Output
    104 
    105 ```
    106 18
    107 10
    108 0
    109 22
    110 ```