Cod sursa(job #72178)

Utilizator peanutzAndrei Homorodean peanutz Data 12 iulie 2007 23:37:38
Problema Oite Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <stdio.h>
#define NMAX 1030
#define MOD 310033
#include <algorithm>
#include <vector>
#define pb push_back
using namespace std;

int a[NMAX];
vector<int> x[MOD], y[MOD];
long long nr;
int n, l;

void read()
{
	int i;
	scanf("%d%d", &n, &l);
	for(i = 1; i <= n; ++i)
		scanf("%d", &a[i]);
}

inline void insert(int i, int j)
{
         int h = (a[i] + a[j]) % MOD;
		
	    x[h].pb(i);

        y[h].pb(j);
        ///printf("am bagat in hash %d si %d la pozitia %d\n", i, j, h);
}	

void fillhash()
{
	int i, j;
	for(i = 1; i < n; ++i)
		for(j = i+1; j <= n; ++j)
			insert(i, j);
}

void solve()
{
	int i, j, k;
	int s, dif, until;

	for(i = 1; i < n; ++i)
		for(j = i+1; j <= n; ++j)
		{	
			s = a[i] + a[j];
			dif = l - s;
            dif %= MOD;


            //printf("caut dif = %d pentru %d si %d\n", dif, i, j);
			for(k = 0, until = x[dif].size(); k < until; ++k)
			{
				if(a[ x[dif][k] ] + a[ y[dif][k] ] == dif  &&  x[dif][k] > j && y[dif][k]  > i)
				{
                    ++nr;
                    //printf("am gasit %d si %d\n", x[dif][k], y[dif][k]);
                }
			}
            //printf("\n\n");
		}
}

int main()
{
	freopen("oite.in", "r", stdin);
	freopen("oite.out", "w", stdout);
	
	read();

	fillhash();

	solve();

	printf("%lld\n", nr);

	return 0;
}