Cod sursa(job #2801447)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 16 noiembrie 2021 11:34:14
Problema Oite Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <bits/stdc++.h>

using namespace std;

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

using ll = long long;

const int MOD = 666013;

struct Hash {
  vector<vector<int>> h;
  void add(int x) {
    int xh = (ll)37 * x % MOD;
    h[xh].push_back(x);
  }
  int count(int x) {
    int xh = (ll)37 * x % MOD;
    int ans = 0;
    for (int val : h[xh])
      if (val == x)
        ans++;
    return ans;
  }
  Hash() : h(MOD, vector<int>{}) {}
};

int main() {
  int n, l; in >> n >> l;
  vector<int> a(n);
  for (int &x : a)
    in >> x;
  sort(a.begin(), a.end());
  Hash H;
  ll ans = (ll)0;
  for (int i = 0; i < n - 1; i++) {
    for (int j = i + 1; j < n; j++)
      if (l - a[i] - a[j] < 0)
        break;
      else {
        int x = l - a[i] - a[j];
        ans += H.count(x);
      }
    for (int j = 0; j < i; j++)
      H.add(a[i] + a[j]);
  }
  out << ans << "\n";
  return 0;
}