codeforces-scrape

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

2158C.md (3347B)


      1 Source: https://codeforces.com/problemset/problem/2158/C
      2 
      3 C. Annoying Game
      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 You are given two integer arrays $a$ and $b$, both of length $n$, and a total number of turns $k$.
     22 
     23 Alice and Bob play a game by taking turns modifying array $a$. Alice goes first. The game lasts for exactly $k$ turns.
     24 
     25 On their turn, a player must choose an index $i$ ($1 \leq i \leq n$) and perform one of the following operations:
     26 
     27 * Add: Increase $a_i$ by $b_i$, i.e., set $a_i := a_i + b_i$.
     28 * Subtract: Decrease $a_i$ by $b_i$, i.e., set $a_i := a_i - b_i$.
     29 
     30 After the $k$-th turn is complete, the final score is calculated as the maximum non-empty subarray sum of the modified array $a$. Alice's goal is to maximize the final score, while Bob's goal is to minimize the final score.
     31 
     32 Assuming both players play optimally to achieve their respective goals, determine the final score.
     33 
     34 The maximum non-empty subarray sum of $a$ is defined as $\max_{1 \leq i \leq j \leq n} S(i, j)$, where $S(i, j) = a_i + a_{i+1} + \cdots + a_j$. Note that empty subarrays are not considered.
     35 
     36 Input
     37 
     38 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     39 
     40 The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2\cdot 10^5$, $1 \le k \le 2\cdot 10^5$) — the length of the arrays and the total number of turns.
     41 
     42 The second line contains $n$ integers $a_1,a_2,\ldots,a_{n}$ ($-10^9 \le a_i \le 10^9$) — the elements of array $a$.
     43 
     44 The third line contains $n$ integers $b_1,b_2,\ldots,b_{n}$ ($0 \le b_i \le 10^9$) — the elements of array $b$.
     45 
     46 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.
     47 
     48 Output
     49 
     50 For each test case, print a single integer — the final score after $k$ turns, assuming both players play optimally.
     51 
     52 Example
     53 
     54 Input
     55 
     56 ```
     57 5
     58 
     59 5 200000
     60 
     61 3 -1 9 -5 4
     62 
     63 0 0 0 0 0
     64 
     65 4 5
     66 
     67 10 10 10 10
     68 
     69 1 1 1 1
     70 
     71 3 1
     72 
     73 2 -7 3
     74 
     75 1 11 3
     76 
     77 3 2
     78 
     79 2 -7 3
     80 
     81 1 11 3
     82 
     83 1 1
     84 
     85 -3
     86 
     87 2
     88 ```
     89 
     90 Output
     91 
     92 ```
     93 11
     94 
     95 41
     96 
     97 9
     98 
     99 3
    100 
    101 -1
    102 ```
    103 
    104 Note
    105 
    106 For the first test case:
    107 
    108 * Any move can't change the array $a$ because all elements in $b$ are zero.
    109 * The maximum non-empty subarray sum of this final array is $3 + (-1) + 9 = 11$.
    110 
    111 For the second test case, one of the possible optimal sequences of moves is:
    112 
    113 * Alice adds $b_3=1$ to $a_3$. Array $a$ becomes $[10, 10, 11, 10]$.
    114 * Bob subtracts $b_1=1$ from $a_1$. Array $a$ becomes $[9, 10, 11, 10]$.
    115 * Alice adds $b_3=1$ to $a_3$. Array $a$ becomes $[9, 10, 12, 10]$.
    116 * Bob subtracts $b_1=1$ from $a_1$. Array $a$ becomes $[8, 10, 12, 10]$.
    117 * Alice adds $b_4=1$ to $a_4$. Array $a$ becomes $[8, 10, 12, 11]$.
    118 * The maximum non-empty subarray sum of this final array is $8+10+12+11 = 41$.
    119 
    120 For the third test case, one of the possible optimal sequences of moves is:
    121 
    122 * Alice adds $b_2=11$ to $a_2$. Array $a$ becomes $[2, 4, 3]$.
    123 * The maximum non-empty subarray sum of this final array is $2 + 4 + 3 = 9$.
    124 
    125 For the fourth test case, one of the possible optimal sequences of moves is:
    126 
    127 * Alice adds $b_2=11$ to $a_2$. Array $a$ becomes $[2, 4, 3]$.
    128 * Bob subtracts $b_2=11$ from $a_2$. Array $a$ becomes $[2, -7, 3]$.
    129 * The maximum non-empty subarray sum of this final array is $3$.