codeforces-scrape

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

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 ```