Cod sursa(job #480666)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 29 august 2010 02:38:53
Problema Oite Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
#include<list>
#include <iostream>

#define NMAX 1026
#define h 699967

using namespace std;

int A[NMAX];
int NR;
int S,N;

list< pair<int,int> > List[h+1];

inline int hash(int x)
{
	return x%h;
}


void rezolva()
{
	int x,z;
	int f;
	int s1,s2;
	for(int i=1;i<=N-3;i++)
		for(int j=i+1;j<=N-2;j++)
		{
			x=S-(A[i]+A[j]);
			if(x>0)
			{
				z=hash(x);
				if(!List[z].empty())
					for(list<pair<int,int> >::iterator itr=List[z].begin();itr!=List[z].end();++itr)
					{
						f=itr->first;
						s1=itr->second%10000;
						s2=itr->second/10000;
						if(f == x && j< s2)
						{
							if(s2 != i && s1 != i)
								if(s2 != j && s1 !=j)
								{
									NR++;
								}
						}
					}
			}
		}
}

void init()
{
	for(int i=3;i<=N-1;i++)
		for(int j=i+1;j<=N;j++)
		{
			List[hash(A[i]+A[j])].push_back(make_pair(A[i]+A[j],i*10000+j));
		}
}

void citire()
{
	fstream fin("oite.in",ios::in);
	
	fin>>N>>S;
	
	for(register int i=1;i<=N;i++)
		fin>>A[i];
	
	fin.close();
}

void afisare()
{
	fstream fout("oite.out",ios::out);
	
	fout<<NR<<"\n";
	
	fout.close();
}

int main(int argc, char* argv[])
{
	citire();
	
	init();
	
	rezolva();
	
	afisare();
}