Cod sursa(job #1226730)

Utilizator george_stelianChichirim George george_stelian Data 7 septembrie 2014 00:03:27
Problema Oite Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn=1<<20,prim=41;
int v[1100],h[maxn],vaz[maxn],n,i,j,l,sol,k;

int inc(int i)
{
    if(++i==maxn) i=0;
    return i;
}

void hash_insert(int x)
{
    //int i=((x%maxn)*prim)%maxn;
    int i=x%maxn;
    while(h[i]>-1 && h[i]!=x) i=inc(i);
    h[i]=x;
    vaz[i]++;
}

int hash_find(int x)
{
    //int i=((x%maxn)*prim)%maxn;
    int i=x%maxn;
    while(h[i]!=-1 && h[i]!=x) i=inc(i);
    if(h[i]==x) return i;
    else return -1;
}

int main()
{
    freopen("oite.in", "r", stdin);
    freopen("oite.out", "w", stdout);
    scanf("%d%d",&n,&l);
    memset(h,-1,sizeof h);
    for(i=1;i<=n;i++) scanf("%d",&v[i]);
    for(i=3;i<n;i++)
    {
        for(j=1;j<i-1;j++) hash_insert(v[j]+v[i-1]);
        for(j=i+1;j<=n;j++)
            if(l-v[i]-v[j]>=0)
            {
                k=hash_find(l-v[i]-v[j]);
                if(k>-1) sol+=vaz[k];
            }
    }
    printf("%d",sol);
    return 0;
}