codeforces-scrape

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

1844C.md (2397B)


      1 Source: https://codeforces.com/problemset/problem/1844/C
      2 
      3 C. Particles
      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 have discovered $n$ mysterious particles on a line with integer charges of $c_1,\dots,c_n$. You have a device that allows you to perform the following operation:
     22 
     23 * Choose a particle and remove it from the line. The remaining particles will shift to fill in the gap that is created. If there were particles with charges $x$ and $y$ directly to the left and right of the removed particle, they combine into a single particle of charge $x+y$.
     24 
     25 For example, if the line of particles had charges of $[-3,1,4,-1,5,-9]$, performing the operation on the $4$th particle will transform the line into $[-3,1,9,-9]$.
     26 
     27  ![](https://espresso.codeforces.com/e03b7cd1557bc6141aa5ceb08d033c7fb1f3d7a9.png) 
     28 
     29 If we then use the device on the $1$st particle in this new line, the line will turn into $[1,9,-9]$.
     30 
     31 You will perform operations until there is only one particle left. What is the maximum charge of this remaining particle that you can obtain?
     32 
     33 Input
     34 
     35 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.
     36 
     37 The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$).
     38 
     39 The second line of each test case contains $n$ integers $c_1,\dots,c_n$ ($-10^9 \le c_i \le 10^9$).
     40 
     41 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     42 
     43 Output
     44 
     45 For each test case, output one integer, the maximum charge of the remaining particle.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 3
     53 
     54 6
     55 
     56 -3 1 4 -1 5 -9
     57 
     58 5
     59 
     60 998244353 998244353 998244353 998244353 998244353
     61 
     62 1
     63 
     64 -2718
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 9
     71 2994733059
     72 -2718
     73 ```
     74 
     75 Note
     76 
     77 In the first test case, the best strategy is to use the device on the $4$th particle, then on the $1$st particle (as described in the statement), and finally use the device on the new $3$rd particle followed by the $1$st particle.
     78 
     79 In the second test case, the best strategy is to use the device on the $4$th particle to transform the line into $[998244353,998244353,1996488706]$, then on the $2$nd particle to transform the line into $[2994733059]$. Be wary of integer overflow.
     80 
     81 In the third test case, there is only one particle, so no operations can be performed.