Cod sursa(job #521527)

Utilizator mgntMarius B mgnt Data 12 ianuarie 2011 19:23:37
Problema Oite Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;

struct Node{int v,f;Node*n;};

typedef long long int lli;
int const maxn=1024,maxv=500*1000*1000;
int C,L,A[maxn];

Node S[2+(maxn*(maxn-1))/2];
int N;

int solve()
{	int s,t,v;
	lli c;Node*q;
	make_heap(A,A+C);
	sort_heap(A,A+C);
	// A[i]<=A[j]<=A[s]<=A[t]
	// i<j<s<t
	// A[i]+A[j]+A[s]+A[t]=L
	map<int,int> m;
	c=0;
	for(s=0;C>s;++s)
	{	q=&S[0];
		for(t=s+1;C>t;++t)
		{	v=A[s]+A[t];
			if(((L/2)<=v)&&(v<=L))
			{	if(m.find(L-v)!=m.end())
				{c+=m[L-v];}
			}
		}
		for(t=0;t<s;++t)
		{++m[A[t]+A[s]];}
	}
	return c;
}

int main()
{	freopen("oite.in","r",stdin);
	freopen("oite.out","w",stdout);
	scanf("%d %d",&C,&L);int i;
	for(i=0;C>i;++i){scanf("%d",&A[i]);}
	lli ans=solve();
	printf("%lld\n",ans);
	return 0;
}