codeforces-scrape

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

1984C1.md (1784B)


      1 Source: https://codeforces.com/problemset/problem/1984/C1
      2 
      3 C1. Magnitude (Easy Version)
      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 The two versions of the problem are different. You may want to read both versions. You can make hacks only if both versions are solved.
     22 
     23 You are given an array $a$ of length $n$. Start with $c = 0$. Then, for each $i$ from $1$ to $n$ (in increasing order) do exactly one of the following:
     24 
     25 * Option $1$: set $c$ to $c + a_i$.
     26 * Option $2$: set $c$ to $|c + a_i|$, where $|x|$ is the absolute value of $x$.
     27 
     28 Let the maximum final value of $c$ after the procedure described above be equal to $k$. Find $k$.
     29 
     30 Input
     31 
     32 The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
     33 
     34 The first line of each test case contains a single integer $n$ ($2 \leq n \leq 2 \cdot 10^5$).
     35 
     36 The second line of each case contains $n$ integers $a_1$, $a_2$, $a_3$, $\ldots$, $a_n$ ($-10^9 \leq a_i \leq 10^9$).
     37 
     38 The sum of $n$ over all test cases does not exceed $3 \cdot 10^5$.
     39 
     40 Output
     41 
     42 For each test case, output a single integer — the value of $k$.
     43 
     44 Example
     45 
     46 Input
     47 
     48 ```
     49 5
     50 
     51 4
     52 
     53 10 -9 -3 4
     54 
     55 8
     56 
     57 1 4 3 4 1 4 3 4
     58 
     59 3
     60 
     61 -1 -2 -3
     62 
     63 4
     64 
     65 -1000000000 1000000000 1000000000 1000000000
     66 
     67 4
     68 
     69 1 9 8 4
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 6
     76 24
     77 6
     78 4000000000
     79 22
     80 ```
     81 
     82 Note
     83 
     84 In the first test case, if we set $c$ to its absolute value every time we add to it, we end up with $6$. It can be shown that this is the maximum result.
     85 
     86 In the second test case, taking the absolute value will never change anything, so we can just sum the array without doing anything to get $24$.
     87 
     88 In the third test case, it is optimal to wait until the end to set $c$ to its absolute value, resulting in an answer of $6$.