Cod sursa(job #76141)

Utilizator DastasIonescu Vlad Dastas Data 8 august 2007 14:57:52
Problema Oite Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <cstdio>
#include <vector>

using namespace std;

#define maxn 1024
#define maxp 204729

FILE *in = fopen("oite.in", "r"), *out = fopen("oite.out", "w");

struct hash
{
    short i, nr;
    int sum;
    hash *next;
};

int n;
int L;
int a[maxn];
hash *h[maxp] = {NULL};

void hadd(int p, int q)
{
    int v = a[p] + a[q];
    int t = v % maxp;

    if ( h[t] )
        if ( h[t]->i == p && h[t]->sum == v )
        {
            ++h[t]->nr;
            return;
        }

    hash *tt = new hash;
    tt->nr = 1;
    tt->i = p;
    tt->sum = v;
    tt->next = h[t];
    h[t] = tt;
}

int hget(int p, int q)
{
    int v = (L - (a[p] + a[q]));
    if ( v < 0 )
        return 0;

    int s = 0;
    int t = v % maxp;

    hash *tt = h[t];

    while ( tt )
    {
        if ( tt->i > q && tt->sum == v )
            s += tt->nr;

        tt = tt->next;
    }

    return s;
}

int main()
{
    fscanf(in, "%d %d", &n, &L);

    for ( int i = 0; i < n; ++i )
        fscanf(in, "%d", &a[i]);

    for ( int i = 0; i < n; ++i )
        for ( int j = i+1; j < n; ++j )
            hadd(i, j);

    int cnt = 0;
    for ( int i = 0; i < n; ++i )
        for ( int j = i+1; j < n; ++j )
            cnt += hget(i, j);


    fprintf(out, "%d\n", cnt);

	return 0;
}