Cod sursa(job #2281552)

Utilizator isav_costinVlad Costin Andrei isav_costin Data 12 noiembrie 2018 14:30:02
Problema Oite Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <cstdio>

#define MAXN 3000000
#define MOD 666019

using namespace std;

int v[MAXN+5];

class Hash
{
  public:
    int x;
    int next[MAXN+5];
    int val[MAXN+5];
    int lista[MOD+5];
    int f[MAXN+5];

  inline void insert( int element )
  {
    x++;

    f[x]=1;
    val[x]=element;
    next[x]=lista[element%MOD];
    lista[element%MOD]=x;
  }

  inline int find( int element )
  {
    int p=lista[element%MOD];

    while( p!=0 && val[p]!=element )
      p=next[p];

    return p;
  }

} h;

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

  int n, l;
  long long ans=0;

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

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

  for( int i=1;i<=n;i++ )
  {
    for( int j=i+1;j<=n;j++ )
      if( l-v[i]-v[j]>=0 )
        ans+=h.f[h.find(l-v[i]-v[j])];

    for( int j=1;j<i;j++ )
      if( h.find(v[i]+v[j])==0 )
        h.insert(v[i]+v[j]);
      else
        h.f[h.find(v[i]+v[j])]++;
  }

  printf( "%lld", ans );

  return 0;
}