COCI '12 Contest 6 #3 Dobri

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 1.0s
Memory limit: 32M

Problem type

You are given a sequence A consisting of N integers. We will call the i^\text{th} sequence element good if it equals the sum of some three elements in positions strictly smaller than i (an element can be used more than once in the sum).

How many good elements does the sequence contain?

Input Specification

The first line of input contains the positive integer N (1 \le N \le 5000), the length of the sequence A.

The second line of input contains N space-separated integers representing the sequence A (-100\,000 \le A_i \le 100\,000).

Output Specification

The first and only line of output must contain the number of good elements in the sequence.

Scoring

In test data worth at least 40\% of total points, N \le 50.

In test data worth at least 70\% of total points, N \le 500.

Sample Input 1

2
1 3

Sample Output 1

1

Sample Input 2

6
1 2 3 5 7 10

Sample Output 2

4

Sample Input 3

3
-1 2 0

Sample Output 3

1

Comments

There are no comments at the moment.