Cod sursa(job #1837397)

Utilizator TincaMateiTinca Matei TincaMatei Data 29 decembrie 2016 17:01:43
Problema Oite Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <cstdio>

const int MOD = (1 << 20) - 1;
const int MAX_N = 1024;
const int PAIRS = MAX_N * MAX_N;
int last[1+MOD], next[1+PAIRS], lana[1+PAIRS], o1[1+PAIRS], o2[1+PAIRS];

inline int hashuie(int x) {
  return x & MOD;
}

void add(int sum, int a, int b, int id) {
  int h;
  h = hashuie(sum);
  next[id] = last[h];
  last[h] = id;
  lana[id] = sum;
  o1[id] = a;
  o2[id] = b;
}

int check(int sum, int a, int b) {
  int h;
  h = hashuie(sum);
  int i = last[h], rez = 0;
  while(i != 0) {
    if(lana[i] == sum && o2[i] < a)
      rez++;
    i = next[i];
  }
  return rez;
}

int v[MAX_N];

int main() {
  int n, l, topkek;
  long long rez;
  FILE *fin = fopen("oite.in", "r");
  fscanf(fin, "%d%d", &n, &l);
  for(int i = 0; i < n; ++i)
    fscanf(fin, "%d", &v[i]);
  fclose(fin);

  rez = 0LL;
  topkek = 1;
  for(int i = 1; i < n; ++i)
    for(int j = 0; j < i; ++j) {
      rez = rez + check(l - v[i] - v[j], j, i);
      add(v[i] + v[j], j, i, topkek);
      topkek++;
    }

  FILE *fout = fopen("oite.out", "w");
  fprintf(fout, "%lld", rez);
  fclose(fout);
  return 0;
}