Cod sursa(job #348411)

Utilizator serbanlupulupulescu serban serbanlupu Data 15 septembrie 2009 19:13:40
Problema Oite Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
//infoarena

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

struct node
{
	short left, right;
	node(int i, int j) {left=i; right=j; }
};

#define PRIM 666203

vector<node > H[PRIM+1];

int v[1050];
short nr_v;
int L;

void read()
{
	fstream f("test.in", ios::in);
	f>>nr_v;
	f>>L;
	for (int i=1; i<=nr_v; ++i)
		f>>v[i];
	f.close();
}

int numar;

void check(int sum, short i, short j)
{
	vector<node >::iterator it;
	for (it=H[sum%PRIM].begin(); it<H[sum%PRIM].end(); it++)
		if ( (v[it->left]+v[it->right]) == sum )
			if (it->right < i)
				++numar;
}

void solve()
{
	for (short i=1; i<nr_v; ++i)
		for (short j=i+1; j<=nr_v; ++j)
		{
			node nou(i, j);
			H[(v[i]+v[j])%PRIM].push_back(nou);
		}
	for (short i=1; i<nr_v; ++i)
		for (short j=i+1; j<=nr_v; ++j)
		{
			int suma=L-v[i]-v[j];
			check(suma, i, j);
		}
	fstream g("test.out", ios::out);
	g<<numar<<" ";
	g.close();
}

int main()
{
	read();
	solve();
	return 0;
}