페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3706

합이 0이 되는 연속구간 세기 1s 512MB

문제

배열 A_1, A_2, A_3, … A_n이 주어졌을 때, 구간 [i,j]에 있어서(1≤i≤j≤n),

a_i + … +a_j 의 합이 0이 되는 모든 경우의 수를 구하는 프로그램을 작성하라

 

 

예를 들어 배열이 {5,-5,-7,7} 라면 답은 {5,-5} , {-7,7} , {5,-5,-7,7}의 3가지이다. 


입력

첫 줄에 배열의 원소 수인 n이 주어진다.(1≤n≤100,000)

 

다음 줄에 공백을 사이에 두고 n개의 배열의 원소들이 순서대로 주어진다. (-100≤a_i≤100) 


출력

한 줄에, 연속구간의 합이 0이 되는 모든 구간의 가짓수를 출력한다.​


예제 #1

4

5 -5 -7 7
3

예제 #2

8
1 0 0 1 -3 1 2 -1
8


출처

ohjtgood

로그인해야 코드를 작성할 수 있어요.