Cod sursa(job #1265149)

Utilizator acomAndrei Comaneci acom Data 16 noiembrie 2014 19:39:42
Problema Oite Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include<fstream>
#include<vector>
using namespace std;
#define NMAX 45001
ifstream fin("oite.in");
ofstream fout("oite.out");
vector < pair <int,int> > v[NMAX];
int n,l,sol,a[1028];
int query(int x)
{
    int i,m=x%NMAX;
    for (i=0;i<v[m].size();++i)
        if (v[m][i].first==x)
            return v[m][i].second;
    return 0;
}
void adauga(int x)
{
    int i,m=x%NMAX;
    for (i=0;i<v[m].size();++i)
        if (v[m][i].first==x)
        {
            ++v[m][i].second;
            return ;
        }
    v[m].push_back(make_pair(x,1));
}
int main()
{
    int i,j;
    fin>>n>>l;
    for (i=1;i<=n;++i)
        fin>>a[i];
    for (i=2;i<n;++i)
    {
        for (j=i+1;j<=n;++j)
        if (l>=a[i]+a[j])
            sol+=query(l-a[i]-a[j]);
        for (j=1;j<i;++j)
            adauga(a[i]+a[j]);
    }
    fout<<sol<<"\n";
    return 0;
}