codeforces-scrape

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

2274B.md (1840B)


      1 Source: https://codeforces.com/problemset/problem/2274/B
      2 
      3 B. Prefix
      4 
      5 time limit per test
      6 
      7 1 second
      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 an array $a_1, a_2, \ldots, a_n$.
     22 
     23 For each index $i = 2, 3, \ldots, n$ in order, perform the following:
     24 
     25 * Define $s = a_1 + a_2 + \ldots + a_{i-1}$.
     26 * Replace $a_i$ with one of the following three values: $a_i - s$, $a_i$, or $a_i + s$.
     27 
     28 Over all possible choices, find the maximum value of $\max(a_1, a_2, \ldots, a_n)$ after the process described above.
     29 
     30 Input
     31 
     32 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.
     33 
     34 The first line of each test case contains a single integer $n$ ($2 \le n \le 50$).
     35 
     36 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-50 \le a_i \le 50$).
     37 
     38 Output
     39 
     40 For each test case, output a single integer — the maximum achievable value of $\max(a_1, a_2, \ldots, a_n)$.
     41 
     42 Please note that the answer for some test cases won't fit into a 32-bit integer type, so you should use at least a 64-bit integer type in your programming language (like long long in C++).
     43 
     44 Example
     45 
     46 Input
     47 
     48 ```
     49 4
     50 
     51 5
     52 
     53 3 -5 1 -4 2
     54 
     55 2
     56 
     57 -1 2
     58 
     59 3
     60 
     61 1 2 3
     62 
     63 3
     64 
     65 -2 -2 -2
     66 ```
     67 
     68 Output
     69 
     70 ```
     71 24
     72 
     73 3
     74 
     75 7
     76 
     77 4
     78 ```
     79 
     80 Note
     81 
     82 In the first test case, the final array can be made $[3, -8, -4, -13, 24]$, so the answer is $24$.
     83 
     84 In the second test case, for $i = 2$, $s = a_1 = -1$. Replacing $a_2$ with $a_2 - s = 2 - (-1) = 3$ gives the answer $3$.
     85 
     86 In the third test case, the final array can be made $[1, 3, 7]$, so the answer is $7$.
     87 
     88 In the fourth test case, replacing $a_2$ with $a_2 + s = -4$ makes $s = -6$ for $i = 3$. Replacing $a_3$ with $a_3 - s = -2 - (-6) = 4$ gives the final array $[-2, -4, 4]$, so the answer is $4$.