codeforces-scrape

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

1903C.md (2467B)


      1 Source: https://codeforces.com/problemset/problem/1903/C
      2 
      3 C. Theofanis' Nightmare
      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 Theofanis easily gets obsessed with problems before going to sleep and often has nightmares about them. To deal with his obsession he visited his doctor, Dr. Emix.
     22 
     23 In his latest nightmare, he has an array $a$ of size $n$ and wants to divide it into non-empty subarrays$^{\dagger}$ such that every element is in exactly one of the subarrays.
     24 
     25 For example, the array $[1,-3,7,-6,2,5]$ can be divided to $[1] [-3,7] [-6,2] [5]$.
     26 
     27 The Cypriot value of such division is equal to $\Sigma_{i=1}^{k} i \cdot \mathrm{sum}_i$ where $k$ is the number of subarrays that we divided the array into and $\mathrm{sum}_i$ is the sum of the $i$-th subarray.
     28 
     29 The Cypriot value of this division of the array $[1] [-3,7] [-6,2] [5] = 1 \cdot 1 + 2 \cdot (-3 + 7) + 3 \cdot (-6 + 2) + 4 \cdot 5 = 17$.
     30 
     31 Theofanis is wondering what is the maximum Cypriot value of any division of the array.
     32 
     33 $^{\dagger}$ An array $b$ is a subarray of an array $a$ if $b$ can be obtained from $a$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.
     34 
     35 Input
     36 
     37 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     38 
     39 Each test case consists of two lines.
     40 
     41 The first line of each test case contains a single integer $n$ ($1 \le n \le 10^{5}$) — the size of the array.
     42 
     43 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^8 \le a_i \le 10^{8}$) — the elements of the array.
     44 
     45 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^{5}$.
     46 
     47 Output
     48 
     49 For each test case, print one integer — the maximum Cypriot value of the array $a$.
     50 
     51 Example
     52 
     53 Input
     54 
     55 ```
     56 4
     57 
     58 6
     59 
     60 1 -3 7 -6 2 5
     61 
     62 4
     63 
     64 2 9 -5 -3
     65 
     66 8
     67 
     68 -3 -4 2 -5 1 10 17 23
     69 
     70 1
     71 
     72 830
     73 ```
     74 
     75 Output
     76 
     77 ```
     78 32
     79 4
     80 343
     81 830
     82 ```
     83 
     84 Note
     85 
     86 In the first test case, to get the maximum Cypriot value we divide the array into $[1][-3][7][-6][2][5]$ which gives us: $\Sigma_{i=1}^{k} i \cdot \mathrm{sum}_i = 1 \cdot 1 + 2 \cdot (-3) + 3 \cdot 7 + 4 \cdot (-6) + 5 \cdot 2 + 6 \cdot 5 = 32$
     87 
     88 Similarly, in the second test case we divide the array into $[2][9,-5,-3]$ which gives us $\Sigma_{i=1}^{k} i \cdot \mathrm{sum}_i = 1 \cdot 2 + 2 \cdot (9 + (-5) + (-3)) = 4$.