codeforces-scrape

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

2173B.md (2255B)


      1 Source: https://codeforces.com/problemset/problem/2173/B
      2 
      3 B. Niko's Tactical Cards
      4 
      5 time limit per test
      6 
      7 1.5 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 Niko is playing a game. Her score is denoted by an integer $k$ which is $0$ initially.
     22 
     23 The game has $n$ turns. On the $i$-th turn, Niko is given a red card with an integer $a_i$ on it, as well as a blue card with an integer $b_i$ on it. She must choose exactly one of the cards and update her score according to her choice:
     24 
     25 * If she chooses the red card, her score becomes $k - a_i$, where $k$ is her score before the turn.
     26 * If she chooses the blue card, her score becomes $b_i - k$, where $k$ is her score before the turn.
     27 
     28 After this, the game proceeds to the next turn, or ends if it is the $n$-th turn.
     29 
     30 Your task is to find the maximum possible score Niko can obtain at the end of the game.
     31 
     32 Input
     33 
     34 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). The description of the test cases follows.
     35 
     36 The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the number of turns.
     37 
     38 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$).
     39 
     40 The third line of each test case contains $n$ integers $b_1, b_2, \ldots, b_n$ ($-10^9 \le b_i \le 10^9$).
     41 
     42 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     43 
     44 Output
     45 
     46 For each test case, output a single integer — the maximum possible score Niko can obtain at the end of the game.
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 3
     54 
     55 3
     56 
     57 4 -8 -1
     58 
     59 -3 -7 0
     60 
     61 5
     62 
     63 -3 1 0 7 1
     64 
     65 -5 3 -1 4 -5
     66 
     67 5
     68 
     69 -7 7 5 4 9
     70 
     71 -9 -3 3 2 2
     72 ```
     73 
     74 Output
     75 
     76 ```
     77 6
     78 12
     79 27
     80 ```
     81 
     82 Note
     83 
     84 In the first test case, one optimal strategy is as follows:
     85 
     86 |  |  |  |  |  |
     87 | --- | --- | --- | --- | --- |
     88 | Turn | 0 | 1 | 2 | 3 |
     89 | Card Chosen | — | Blue | Red | Red |
     90 | Score | $0$ | $-3 - 0 = -3$ | $-3 - (-8) = 5$ | $5 - (-1) = 6$ |
     91 
     92  In the second test case, one optimal strategy is as follows: 
     93 
     94 |  |  |  |  |  |  |  |
     95 | --- | --- | --- | --- | --- | --- | --- |
     96 | Turn | 0 | 1 | 2 | 3 | 4 | 5 |
     97 | Card Chosen | — | Blue | Blue | Blue | Blue | Red |
     98 | Score | $0$ | $-5$ | $8$ | $-9$ | $13$ | $12$ |