시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 1445 233 155 17.033%

문제

$N$개의 정수 수열 $A_1, A_2, \dots , A_N$이 주어진다. 수열을 각각이 연속된 네 부분으로 나누려고 한다. 단, 각 부분은 최소 하나의 수를 포함해야 한다. 또, 각 부분의 합은 모두 같아야 한다. 즉, 어떤 $i, j, k$ ($1 \le i < j < k < N$)에 대해서 $[A_1, \dots, A_i], [A_{i+1}, \dots, A_j], [A_{j+1}, \dots, A_k], [A_{k+1}, \dots, A_N]$으로 나눈다.

예를 들어 주어진 수열이 $4, −1, 2, 1, −3, 1, 2, 2, 1, 3$이라고 하자. 이 수열을 아래와 같이 나누면 각 부분의 합이 달라서 허용되는 형태가 아니다.

$[4, −1, 2], [1, −3, 1, 2], [2, 1], [3]$

아래과 같이 나눈 경우 각 부분의 합이 모두 같다.

$[4, −1], [2, 1], [−3, 1, 2, 2, 1], [3]$

아래와 같이 나눈 경우들도 각 부분의 합이 모두 같다.

$[4, −1], [2, 1, −3, 1, 2], [2, 1], [3]$ 혹은 $[4, −1, 2, 1, −3], [1, 2], [2, 1], [3]$

수열을 입력 받아 위와 같이 나눌 수 있는 가능한 방법의 개수를 계산하는 프로그램을 작성하라.

입력

첫 번째 줄에 수열의 길이 $N$이 주어진다.

두 번째 줄에 $N$개의 정수 $A_1, A_2, \dots , A_N$이 공백 하나씩을 사이로 두고 주어진다.

출력

첫 번째 줄에 가능한 방법의 개수를 출력한다.

출력 값이 매우 클 수 있으므로 C, C++ 언어에서는 long long 형의 변수를, Java에서는 long 형의 변수를 사용해야 한다.

제한

  • $4 \le N \le 100~000$
  • 모든 $1 \le i \le N$에 대해 $-1~000 \le A_i \le 1~000$

서브태스크

번호 배점 제한
1 5

모든 $1 \le i \le N$에 대해 $A_i = 0$

2 7

모든 $1 \le i \le N$에 대해 $A_i > 0$

3 4

모든 $1 \le i \le N$에 대해 $A_i \ge 0$

4 11

$N \le 10$

5 19

$N \le 500$

6 23

$N \le 5~000$

7 31

추가 제약 조건 없음

예제 입력 1

4
1 1 1 1

예제 출력 1

1

예제 입력 2

10
4 -1 2 1 -3 1 2 2 1 3

예제 출력 2

3

채점 및 기타 정보

  • 예제는 채점하지 않는다.