Cod sursa(job #1144283)

Utilizator felixiPuscasu Felix felixi Data 16 martie 2014 20:48:22
Problema Oite Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int MOD= 666013, NMAX= 1034;

struct HASH{
    int x,y;
};

vector <HASH> H[ MOD+2 ];

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

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

inline int RASP( HASH aux, int sum ) {
    if( sum >= 0 ) {
        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;
    }
    return 0;
}

inline int next_int() {
    char c;
    int nr= 0;
    in.get(c);
    while( c>47 && c<58 ) {
        nr= nr*10 + c-48;
        in.get(c);
    }
    return nr;
}

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

    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;
}