2244D.md (2077B)
1 Source: https://codeforces.com/problemset/problem/2244/D 2 3 D. Yaroslav and Productivity 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 Yaroslav's productivity during the day is described by an array $a$ of length $n$. His productivity can be negative if he watches short videos, or positive if he works. The total productivity is defined as the sum of all values in the array. 22 23 Sometimes Yaroslav reads motivational posts. He has $m$ posts, where the $j$-th post has an impact value $b_j$. If Yaroslav reads a post with value $b_j$, then all productivity values from the beginning of the day up to position $b_j$ change sign, that is, all integers $a_1, a_2, a_3, \dots, a_{b_j}$ are multiplied by $-1$. 24 25 For example, let $a = [1, -4, 3, -4]$, and Yaroslav reads a post with value $3$. Then the signs of the first three elements are flipped, and the array becomes $[-1, 4, -3, -4]$. If he then reads a post with value $1$, the first element changes sign again, and the array becomes $[1, 4, -3, -4]$. 26 27 What is the maximum possible total productivity Yaroslav can achieve by reading any (possibly none) of the posts? 28 29 Input 30 31 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 32 33 The first line of each test case contains two integers $n$ and $m$ ($1 \le m \le n \le 2 \cdot 10^5$) — the number of measurements and the number of motivational posts. 34 35 The second line of each test case contains $n$ integers $a_i$ ($-10^9 \le a_i \le 10^9$) — the productivity values. 36 37 The third line of each test case contains $m$ integers $b_i$ ($1 \le b_i \le n$) — the impact values of the posts. It is guaranteed that all $b_i$ are distinct. 38 39 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 40 41 Output 42 43 For each test case, output a single integer — the maximum possible total productivity. 44 45 Example 46 47 Input 48 49 ``` 50 4 51 52 5 3 53 54 -1 2 -3 4 -5 55 56 1 5 3 57 58 4 2 59 60 3 -1 3 -1 61 62 4 2 63 64 3 1 65 66 -5 -5 -5 67 68 2 69 70 4 3 71 72 3 -1 1 -3 73 74 4 3 2 75 ``` 76 77 Output 78 79 ``` 80 3 81 82 4 83 84 5 85 86 6 87 ```