Cod sursa(job #1257618)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 7 noiembrie 2014 23:09:25
Problema Oite Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <fstream>
#include <vector>
#define DIM 1030
#define mod 666013
#define x first
#define y second
#define pint vector< pair<int, int> >::iterator
#define infile "oite.in"
#define outfile "oite.out"

using namespace std;

ifstream f(infile);
ofstream g(outfile);

vector< pair<int, int> > Hash[mod];

int Sum, n;

int v[DIM];

int main() {
	f >> n >> Sum;
	for (int i = 1; i <= n; ++i)
		f >> v[i];
	long long SOL = 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = i + 1; j <= n; ++j) {
			int sum = Sum - v[i] - v[j];
			if (sum < 0)
				continue;
			int hash = sum % mod;
			for (pint it = Hash[hash].begin(); it != Hash[hash].end(); ++it)
				if (it->x == sum)
					SOL += it->y;
		}
		for (int j = 1; j < i; ++j) {
			int sum = v[i] + v[j];
			if (sum > Sum)
				continue;
			int hash = sum % mod;
			bool ok = false;
			for (pint it = Hash[hash].begin(); it != Hash[hash].end(); ++it) {
				if (it->x == sum) {
					ok = true;
					++it->y;
					break;
				}
			}
			if (!ok)
				Hash[hash].push_back(make_pair(sum, 1));
		}
	}
	g << SOL;
	return 0;
}

//Trust me, I'm the Doctor!