codeforces-scrape

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

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