Cod sursa(job #1120445)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 25 februarie 2014 00:15:37
Problema Oite Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<cstdio>
#include<vector>
#include<cassert>

using namespace std;

typedef long long int lld;
typedef pair<int,int> PII;
const int MOD = 666013;
const int NMAX = 1030;

struct Hash
{
    vector<PII> H[MOD+10];

    void Adauga(lld x,int j)
    {
        int r=x%MOD;
        H[r].push_back(make_pair(x,j));
    }

    int Cauta(lld x,int i)
    {
        if(x<0) return 0;
        int r=x%MOD,ans=0;
        vector<PII>::iterator it;
        for(it=H[r].begin(); it!=H[r].end(); it++)
            if(it->first==x && it->second<i) ans++;
        return ans;
    }
};

int N,Sol;
lld A[NMAX],L;
Hash H;

int main()
{
    int i,j;

    freopen("oite.in","r",stdin);
    freopen("oite.out","w",stdout);

    scanf("%d%lld",&N,&L);

    for(i=1; i<=N; i++)
        scanf("%lld",&A[i]);

    for(i=1; i<=N; i++)
        for(j=i+1; j<=N; j++)
        {
            if(A[i]+A[j]>L) continue;
            H.Adauga(A[i]+A[j],j);
            Sol+=H.Cauta(L-A[i]-A[j],i);
        }

    printf("%d\n",Sol);

    return 0;
}