2033D.md (1359B)
1 Source: https://codeforces.com/problemset/problem/2033/D 2 3 D. Kousuke's Assignment 4 5 time limit per test 6 7 2 seconds 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 After a trip with Sakurako, Kousuke was very scared because he forgot about his programming assignment. In this assignment, the teacher gave him an array $a$ of $n$ integers and asked him to calculate the number of non-overlapping segments of the array $a$, such that each segment is considered beautiful. 22 23 A segment $[l,r]$ is considered beautiful if $a_l + a_{l+1} + \dots + a_{r-1} + a_r=0$. 24 25 For a fixed array $a$, your task is to compute the maximum number of non-overlapping beautiful segments. 26 27 Input 28 29 The first line of input contains the number $t$ ($1 \le t \le 10^4$) — the number of test cases. Each test case consists of $2$ lines. 30 31 * The first line contains one integer $n$ ($1 \le n \le 10^5$) — the length of the array. 32 * The second line contains $n$ integers $a_i$ ($-10^5 \le a_i \le 10^5$) — the elements of the array $a$. 33 34 It is guaranteed that the sum of $n$ across all test cases does not exceed $3\cdot 10^5$. 35 36 Output 37 38 For each test case, output a single integer: the maximum number of non-overlapping beautiful segments. 39 40 Example 41 42 Input 43 44 ``` 45 3 46 47 5 48 49 2 1 -3 2 1 50 51 7 52 53 12 -4 4 43 -3 -5 8 54 55 6 56 57 0 -4 0 3 0 1 58 ``` 59 60 Output 61 62 ``` 63 1 64 2 65 3 66 ```