Cod sursa(job #741717)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 26 aprilie 2012 20:03:30
Problema Oite Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

#define HASH 10007
#define MAXN 2000

vector<pair<int, int> > G[HASH];
vector<pair<int, int> >::iterator it;
int A[MAXN];
int i, j;
int N, L, Ans;

inline int Caut(const int &val)
{
	if (val < 0) return 0;
	int mod = val % HASH;
	for (it = G[mod].begin(); it != G[mod].end(); ++it)
		if ((*it).first == val)
			return (*it).second;
	return 0;
}

inline void Inserez(const int &val)
{
	if (val < 0) return;
	int mod = val % HASH;
	for (it = G[mod].begin(); it != G[mod].end(); ++it)
		if ( (*it).first == val){
			++((*it).second);
			return;
		}
	G[mod].push_back( make_pair(val, 1));
}

int main()
{
	freopen("oite.in","r",stdin);
	freopen("oite.out", "w",stdout);
	
	scanf("%d %d",&N,&L);
	for (i=1; i<=N; ++i)
		scanf("%d",&A[i]);
	sort(A+1, A+N+1);
	
	Ans = 0;
	for (i = 1; i <= N; ++i){
		for (j = i + 1; j <= N; ++j)
			Ans += 1LL * Caut(L - A[i] - A[j]);
		for (j = 1; j < i; ++j)
			Inserez(A[i] + A[j]);
	}
	
	printf("%d\n", Ans);
	
	return 0;
}