Cod sursa(job #1144276)

Utilizator felixiPuscasu Felix felixi Data 16 martie 2014 20:42:05
Problema Oite Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream in("oite.in");
ofstream out("oite.out");

const int MOD= 666013, NMAX= 1024;

struct HASH{
    int x,y;
};

vector <HASH> H[ MOD+1 ];

int v[ NMAX+1 ];
int N, S;

inline int key( int n ) {
    return n % MOD;
}

inline int RASP( HASH aux, int sum ) {
    int k= key( sum );
    int gasit= 0;
    for( int i= 0;  i<(int)H[k].size();  i++ ) {
        if( sum == v[ H[k][i].x ] + v[ H[k][i].y ] ) {
            if( aux.y < H[k][i].x ) {
                gasit++;
            }
        }
    }
    return gasit;
}

int main()
{
    in >> N >> S;
    for( int i=1; i<=N; i++ ) {
        in >> v[i];
    }

    for( int i= 1;  i<N;  i++ ) {
        for( int j= i+1;  j<=N;  j++ ) {
            HASH aux;
            int k= key( v[i]+v[j] );
            aux.x= i;    aux.y= j;
            H[ k ].push_back( aux );
        }
    }

    int sol= 0;
    for( int i= 1;  i<N;  i++ ) {
        for( int j= i+1;  j<=N;   j++ ) {
            HASH aux;
            aux.x= i;   aux.y= j;
            int k= RASP( aux, S-v[i]-v[j] );
            sol+= k;
        }
    }

    out << sol << '\n';

    return 0;
}