Cod sursa(job #497518)

Utilizator Addy.Adrian Draghici Addy. Data 2 noiembrie 2010 18:30:44
Problema Oite Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <cstdio>
#include <vector>

using namespace std;

const int MOD = 9901;
const int NMAX = 1048;

int V[NMAX], A[MOD], n, x, i, j, k, a, b, c, nr;
vector <pair <int, pair <int, int> > > H[MOD];

int cauta (int);
void adauga (int, int, int), sterge (int, int, int);

int main () {
	
	freopen ("oite.in", "r", stdin);
	freopen ("oite.out", "w", stdout);
	
	scanf ("%d %d", &n, &x);
	
	for (i = 1; i <= n; i++)
		scanf ("%d", &V[i]);
	
	for (i = 3; i < n; i++)
		for (j = i + 1; j <= n; j++) {
			a = V[i] + V[j];
			adauga (a, i, j);
		}
	
	for (k = 2; k < n - 1; k++) {
		for (i = 1; i < k; i++) {
			a = V[i] + V[k];
			nr += cauta (x - a);
		}
		
		for (i = k + 2; i <= n; i++) {
			a = V[k+1] + V[i];
			sterge (a, k+1, i);
		}
	}
	
	printf ("%d", nr);
	
	return 0;
}

void adauga (int v, int x, int y) {
	
	int p = v % MOD;
	
	H[p].push_back (make_pair (v, make_pair (x, y)));
}

int cauta (int v) {
	
	int p = v % MOD, nr = 0;
	vector <pair <int, pair <int, int> > >::iterator it;
	
	for (it = H[p].begin (); it != H[p].end (); it++)
		if ((*it).first == v) {
			while (it != H[p].end () && (*it).first == v) {
				nr++;
				it++;
			}
			break;
		}
	
	return nr;
}

void sterge (int v, int x, int y) {
	
	int p = v % MOD;
	vector <pair <int, pair <int, int> > >::iterator it;
	
	for (it = H[p].begin (); it != H[p].end (); it++)
		if ((*it).first == v && (*it).second.first == x && (*it).second.second == y) {
			H[p].erase (it);
			
			return;
		}
}