Cod sursa(job #2216818)

Utilizator PinkiePie1189Preoteasa Mircea-Costin PinkiePie1189 Data 28 iunie 2018 02:13:31
Problema Oite Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include<stdio.h>
#include<unordered_map>
#include<utility>
#include<vector>
#define MAX_TERMS 4
#define MAXL 1000000
#define MAXN 1024
FILE*fin,*fout;


void bkt(int level);
int N,L;
long long ans;
int v[MAXN+1];
int sol[MAX_TERMS+1];
//std::unordered_map<int,std::vector<std::pair<int,int> > > mp;

std::vector<std::pair<int,int> > mp[4*MAXL+1];
int main()
{
    fin=fopen("oite.in","r");
    fout=fopen("oite.out","w");

    fscanf(fin,"%d%d",&N,&L);

    for(int i=1;i<=N;i++)
    {
        fscanf(fin,"%d",&v[i]);
    }
    for(int i=1;i<=N;i++)
    {
        for(int j=i+1;j<=N;j++)
        {
            mp[v[i]+v[j]].push_back(std::make_pair(i,j));
        }
    }
    for(int i=1;i<=N;i++)
    {
        for(int j=i+1;j<=N;j++)
        {
            std::vector<std::pair<int,int > >::iterator beg=mp[L-v[i]-v[j]].begin();
            std::vector<std::pair<int,int > >::iterator fin=mp[L-v[i]-v[j]].end();
            for(std::vector<std::pair<int,int> >::iterator it=beg;it!=fin;it++)
            {
                if(i!=(it->first) && j!=(it->first) && i!=(it->second) && j!=(it->second))
                {
                    ans++;
                }
            }
        }
    }
    fprintf(fout,"%lld",ans/6);
    fclose(fin);
    fclose(fout);

    return 0;
}

void bkt(int level)
{
    if(level==MAX_TERMS+1)
    {
        long long sum=0;
        for(int i=1;i<=MAX_TERMS;i++)
        {
            sum+=v[sol[i]];
        }
        if(sum==L)
        {
            ans++;
        }
    }
    else
    {
        for(int i=sol[level-1]+1;i<=N-MAX_TERMS+level;i++)
        {
            sol[level]=i;
            bkt(level+1);
        }
    }
}