Cod sursa(job #44705)

Utilizator victorsbVictor Rusu victorsb Data 31 martie 2007 17:21:42
Problema Oite Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <cstdio>
#include <vector>

using namespace std;

#define Nmax 1024
#define Tmax 654321
#define pb push_back
#define mp make_pair
#define sz size()
#define x first
#define y second

int n, l;
int sir[Nmax];
vector< pair<int, int> > T[Tmax];

void citire()
{
    int i;
    
    scanf("%d %d", &n, &l);
    for (i = 1; i <= n; ++i)
        scanf("%d", &sir[i]);
}

void update(int vl)
{
    int i, h;
    
    h = (vl << 4) ^ (vl >> 28);
    h = abs(h) % Tmax;
    
    for (i = 0; i < T[h].sz; ++i)
        if (T[h][i].x == vl)
        {
            ++T[h][i].y;
            return;
        }
    
    T[h].pb( mp(vl, 1) );
}

int find(int vl)
{
    int i, h;
    
    h = (vl << 4) ^ (vl >> 28);
    h = abs(h) % Tmax;
    
    for (i = 0; i < T[h].sz; ++i)
        if (T[h][i].x == vl)
            return T[h][i].y;
    
    return 0;
}

void solve()
{
    int i, j, sol = 0;
    
    for (i = 1; i <= n; ++i)
    {
        for (j = i + 1; j <= n; ++j)
            if (l - sir[i] - sir[j] >= 0)
                sol += find(l - sir[i] - sir[j]);
        
        for (j = 1; j < i; ++j)
            if (sir[i] + sir[j] <= l)
                update(sir[i] + sir[j]);
    }
    
    printf("%d\n", sol);
}

int main()
{
    freopen("oite.in", "r", stdin);
    freopen("oite.out", "w", stdout);
    citire();
    solve();
    return 0;
}