Cod sursa(job #1060730)

Utilizator Theodor1000Cristea Theodor Stefan Theodor1000 Data 18 decembrie 2013 16:58:49
Problema Oite Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <cstdio>
#include <vector>

#define M 666013
#define pb push_back
#define mp make_pair
#define f first
#define s second

using namespace std;

int v[2048];

vector < pair <int, int> > h[M];

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

    int n, l;
    scanf ("%d %d", &n, &l);

    for (int i = 0; i < M; i++)
        h[i].reserve (5);

    for (int i = 1; i <= n; i++)
        scanf ("%d", &v[i]);

    long long sol = 0;

    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            int nr = v[i] + v[j];
            nr = l - nr;
            if (nr < 0) continue;

            int ind = nr % M;

            for (int q = 0; q < h[ind].size (); q++)
                if (h[ind][q].f == nr) sol += h[ind][q].s;
        }

        for (int j = 1; j < i; j++)
        {
            int nr = v[i] + v[j];
            if (nr > l) continue;

            int ind = nr % M, q;

            for (q = 0; q < h[ind].size (); q++)
                if (h[ind][q].f == nr)
                {
                    h[ind][q].s++;
                    break;
                }

            if (q == h[ind].size ()) h[ind].pb ( mp(nr, 1) );
        }
    }

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

    return 0;
}