Cod sursa(job #348419)

Utilizator serbanlupulupulescu serban serbanlupu Data 15 septembrie 2009 19:27:47
Problema Oite Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
//infoarena

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

using namespace std;

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

#define PRIM 1000001

vector<node > H[PRIM+1];

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

void read()
{
	fstream f("oite.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);
			int suma=v[i]+v[j];
			H[suma%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];
			if (suma > 0)
				check(suma, i, j);
		}
	fstream g("oite.out", ios::out);
	g<<numar<<" ";
	g.close();
}

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