Mai intai trebuie sa te autentifici.
Cod sursa(job #240164)
Utilizator | Data | 6 ianuarie 2009 22:31:00 | |
---|---|---|---|
Problema | Oite | Scor | 10 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.4 kb |
#include <cstdio>
#include <vector>
using namespace std;
#define MOD 666013
#define MAX_N 1025
struct oaie
{
int nr, ind;
int I[MAX_N], J[MAX_N];
};
int N, L, V[MAX_N];
vector <oaie> H[MOD];
long Rez;
void hash(int i, int j)
{
int x = V[i] + V[j];
if(x > L) return;
int k = x % MOD;
for(vector<oaie>::iterator it = H[k].begin(); it != H[k].end(); ++it)
if(it -> nr == x)
{
++it -> ind;
it -> I[it -> ind] = i;
it -> J[it -> ind] = j;
return;
}
oaie w;
w.nr = x, w.ind = 1;
w.I[1] = i, w.J[1] = j;
H[k].push_back(w);
}
int search(int i, int j)
{
int x = L - V[i] - V[j];
int k = x % MOD;
int Sol = 0;
for(vector<oaie>::iterator it = H[k].begin(); it != H[k].end(); ++it)
if(it -> nr == x)
for(int k = 1; k <= it -> ind; ++k)
if(it -> I[k] > j && it -> J[k] != j)
++Sol;
return Sol;
}
void citire()
{
scanf("%d %d",&N, &L);
for(int i = 1; i <= N; ++i)
scanf("%d",V+i);
}
void solve()
{
for(int i = 1; i < N; ++i)
for(int j = i+1; j <= N; ++j)
hash(i, j);
for(int i = 1; i < N; ++i)
for(int j = i+1; j <= N; ++j)
Rez += search(i, j);
printf("%ld\n",Rez);
}
int main()
{
freopen("oite.in","rt",stdin);
freopen("oite.out","wt",stdout);
citire();
solve();
}