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 ( - 105 ≤ Ai ≤ 105).
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
题意
给你一个序列，任意一个数只要等于在它前面的任意三个数之和（可以相同）则称为good数
题解：
有时候能用数组尽量用数组，set还是有*的
代码：
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
#include <typeinfo>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
inline ll read()
{
ll x=,f=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-')f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
//***************************
int s[];
int main()
{
int ans=;
int a[];
int n=read();
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
for(int j=;j<i;j++)
{
if(s[a[i]-a[j]+])
{
ans++;
break;
}
}
for(int j=;j<i;j++)
{
s[a[i]+a[j]+]=;
}
s[a[i]+a[i]+]=;
}
cout<<ans<<endl;
return ;
}