Cod sursa(job #2760170)

Utilizator vlad2009Vlad Tutunaru vlad2009 Data 23 iunie 2021 14:32:34
Problema Oite Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <fstream>

using namespace std;

const int K = 666019;
const int Nmax = 1024 + 1;

int a[Nmax], val[Nmax], urm[Nmax], lst[K], nr;

bool exista(int x)
{
    int categoria = x % K;
    int p = lst[categoria];
    while (p != 0)
    {
        if (val[p] == x)
        {
            return true;
        }
        p = urm[p];
    }
    return false;
}

void adauga(int x)
{
    if (exista(x))
    {
        return;
    }
    val[++nr] = x;
    int categoria = x % K;
    urm[nr] = lst[categoria];
    lst[categoria] = nr;
}

int main()
{
    ifstream fin("oite.in");
    ofstream fout("oite.out");
    int c, l;
    fin >> c >> l;
    for (int i = 0; i < c; i++)
    {
        fin >> a[i];
    }
    for (int i = 0; i < c; i++)
    {
        for (int j = 0; j < c; j++)
        {
            adauga(a[i] + a[j]);
        }
    }
    long long ans = 0;
    for (int i = 0; i < c; i++)
    {
        for (int j = i + 1; j < c; j++)
        {
            if (i != j && a[i] + a[j] <= l)
            {
                if (exista(l - a[i] - a[j]))
                {
                    for (int p = j + 1; p < c; p++)
                    {
                        for (int w = p + 1; w < c; w++)
                        {
                            if (a[i] + a[j] + a[p] + a[w] == l)
                            {
                                ans++;
                            }
                        }
                    }
                }
            }
        }
    }
    fout << ans;
    return 0;
}