Cod sursa(job #332409)

Utilizator klamathixMihai Calancea klamathix Data 17 iulie 2009 18:32:29
Problema Oite Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include<cstdio>
#include<vector>
#define MOD 666017
#define MAXN 1 << 10 + 1

using namespace std;

struct cuplu {
       int A;
       int B;
       int Sum;
       };

cuplu config;
vector <cuplu> Hash[MOD];

int i , j , N , L , A[MAXN] , count;
bool taken[MAXN][MAXN];
int H( int X ) {
    return ( X % MOD );
}

int Search ( int ii , int jj , int Value ) {
    
    int k , x = H ( Value ) , ok = 0 , contor = 0;
    
    for( k = 0 ; k < Hash[x].size() ; ++k ) 
         if ( Hash[x][k].Sum == Value ) 
            if( ii < jj && jj < Hash[x][k].A && Hash[x][k].A <Hash[x][k].B ) 
             {
              //taken[Hash[x][k].A][Hash[x][k].B]  = 1;
             // printf("%d %d %d %d\n",ii , jj , Hash[x][k].A , Hash[x][k].B ) ;
              contor ++;
              
              }
    return contor;
}

int main ()
{
    freopen("oite.in","r",stdin);
    freopen("oite.out","w",stdout);
    
    scanf("%d %d",&N,&L);
    
    for( i = 1 ; i <= N ; ++i )
         scanf("%d",&A[i]);
    
    for( i = 1 ; i <= N ; ++i)
         for( j = i + 1 ; j <= N ; ++j) {
                config.A = i , config.B = j , config.Sum = A[i] + A[j];    
                Hash[H(config.Sum)].push_back( config );
              }
    
    for( i = 1 ; i <= N ; ++i ) 
         for( j = i + 1 ; j <= N ; ++j ) 
              //if ( taken[i][j] == 0 ) 
                  count+= Search( i , j , ( L - ( A[i] + A[j] ) ) ) ;
    
    //for ( i = 0 ; i < Hash[13].size() ; ++i ) 
      //  printf("%d %d\n",Hash[13][i].A , Hash[13][i].B);
    
    printf("%d\n",count );

return 0;
}