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 ```