1405B.md (1619B)
1 Source: https://codeforces.com/problemset/problem/1405/B 2 3 B. Array Cancellation 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're given an array $a$ of $n$ integers, such that $a_1 + a_2 + \cdots + a_n = 0$. 22 23 In one operation, you can choose two different indices $i$ and $j$ ($1 \le i, j \le n$), decrement $a_i$ by one and increment $a_j$ by one. If $i \lt j$ this operation is free, otherwise it costs one coin. 24 25 How many coins do you have to spend in order to make all elements equal to $0$? 26 27 Input 28 29 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 5000$). Description of the test cases follows. 30 31 The first line of each test case contains an integer $n$ ($1 \le n \le 10^5$) — the number of elements. 32 33 The next line contains $n$ integers $a_1, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$). It is given that $\sum_{i=1}^n a_i = 0$. 34 35 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. 36 37 Output 38 39 For each test case, print the minimum number of coins we have to spend in order to make all elements equal to $0$. 40 41 Example 42 43 Input 44 45 ``` 46 7 47 4 48 -3 5 -3 1 49 2 50 1 -1 51 4 52 -3 2 -3 4 53 4 54 -1 1 1 -1 55 7 56 -5 7 -6 -4 17 -13 4 57 6 58 -1000000000 -1000000000 -1000000000 1000000000 1000000000 1000000000 59 1 60 0 61 ``` 62 63 Output 64 65 ``` 66 3 67 0 68 4 69 1 70 8 71 3000000000 72 0 73 ``` 74 75 Note 76 77 Possible strategy for the first test case: 78 79 * Do $(i=2, j=3)$ three times (free), $a = [-3, 2, 0, 1]$. 80 * Do $(i=2, j=1)$ two times (pay two coins), $a = [-1, 0, 0, 1]$. 81 * Do $(i=4, j=1)$ one time (pay one coin), $a = [0, 0, 0, 0]$.