Codeforces Gym 100203G G

G - Good elements
Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=87954#problem/G

Description

You are given a sequence A consisting of N integers. We will call the i-th 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

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

The second line of input contains N space-separated integers representing the sequence A ( - 10⁵ ≤ A_i ≤ 10⁵).

Output

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

Sample Input

2
1 3

Sample Output

1

HINT

题意

给你n个数，问你有多少个good数

每个good数的定义是，这个数如果能被他前面的任意三个数的和构成的话，（可以重复用）就是good数

题解：

n^2预处理出来所有数的两两之间的和，然后再暴力n^2找是否存在这样的和

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <string>
#include <ctime>
#include <list>
#include <bitset>
typedef unsigned char byte;
#define pb push_back
#define input_fast std::ios::sync_with_stdio(false);std::cin.tie(0)
#define local freopen("in.txt","r",stdin)
#define pi acos(-1)

using namespace std;
const int maxn = 5e3 + 50;
const int limit = 1e5;
int p[maxn] , n  , ans = 0 , exist[limit * 6];


int main(int argc,char *argv[])
{
    scanf("%d",&n);
    memset(exist,0,sizeof(exist));
    for(int i = 1 ; i <= n ; ++ i) scanf("%d",p+i);
    exist[p[1]*2 + limit*2] = 1;
    if (p[1] * 3 == p[2]) ans ++;
    exist[p[1] + p[2] + limit*2] = 1;
    exist[p[2] * 2 + limit*2] = 1;
    for(int i = 3 ; i <= n ; ++ i)
    {
        for(int j = 1 ; j < i ; ++ j)
        {
            int dis = p[i] - p[j];
            if (exist[dis+limit*2])
            {
                ans ++;
                break;
            }
        }
        for(int j = 1 ; j < i ; ++ j)
            exist[p[i]+p[j]+limit*2] = 1;
        exist[p[i] * 2 + limit*2] = 1;
    }
    printf("%d
",ans);
    return 0;
}