problem.txt (2073B)
1 C. Zero-Sum Prefixes 2 time limit per test 3 1 second 4 memory limit per test 5 256 megabytes 6 7 The score of an array v1,v2,…,vn is defined as the number of indices i (1≤i≤n) such that v1+v2+…+vi=0. 8 9 You are given an array a1,a2,…,an of length n. You can perform the following operation multiple times: 10 11 select an index i (1≤i≤n) such that ai=0; 12 then replace ai by an arbitrary integer. 13 14 What is the maximum possible score of a that can be obtained by performing a sequence of such operations? 15 Input 16 17 Each test contains multiple test cases. The first line contains a single integer t (1≤t≤104) — the number of test cases. 18 19 The first line of each test case contains one integer n (1≤n≤2⋅105) — the length of the array a. 20 21 The second line of each test case contains n integers a1,a2,…,an (−109≤ai≤109) — array a. 22 23 It is guaranteed that the sum of n over all test cases does not exceed 2⋅105. 24 Output 25 26 For each test case, print the maximum possible score of the array a after performing a sequence of operations. 27 28 --- 29 30 problem: 31 32 - sum := number of indices where all prior values + current == 0 33 - operation 34 - select an index s.t. a[i] == 0 and replace it with any number 35 - we can do this as many times as we want 36 - don't have to though 37 - return max score where we can perform the ops 38 39 --- 40 41 ex1: 42 43 2 0 1 -1 0 44 45 2 2 3 2 2 46 47 2 -2 1 -1 0 48 49 2 0 1 0 0 50 51 heuristic here was to compute the prefix sums, check sums to the right and 52 if number of zeroes < most popular other number, substitute the zero with the 53 inversion of the most popular number. 54 55 ex2: 56 57 1000000000 1000000000 0 58 59 1000000000 2000000000 2000000000 60 61 1000000000 1000000000 -2000000000 62 63 1000000000 2000000000 0 64 65 The heuristic should be inclusive of the a_i index 66 67 ex3: 68 69 0 0 0 0 70 71 0 0 0 0 72 73 4 74 75 ex4: 76 77 3 0 2 -10 10 -30 30 0 78 79 3 3 5 -5 5 -25 5 5 80 81 3 -5 2 -10 10 -30 30 0 82 83 3 -2 0 -10 0 -30 0 0 84 85 We only care about the sums between zeroes 86 87 ex5: 88 89 1 0 0 1 -1 0 1 0 -1 90 91 1 1 1 2 1 1 2 2 1 92 93 1 -1 0 1 -1 0 1 0 -1 94 95 1 0 0 1 0 0 1 1 0 96 97 1 -1 0 1 -1 -1 1 0 -1 98 99 1 0 0 1 0 -1 0 0 -1