FourSum.cpp

#include "bits/stdc++.h"
using namespace std;

const int N = 5000;
const int T = 1000000;
const int V = 1000000000;

int n, t;
int arr[N + 1], hashMap[T + 1];

inline void add(int x) {
    if (x <= t) {
        ++hashMap[x];
    }
}

inline int sum(int x) {
    if (x < 0) {
        return 0;
    }
    return hashMap[x];
}

int main() {
    cin >> n >> t;
    assert((n <= N) && (t <= T));
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        assert(arr[i] <= V);
    }
    if (n < 4) {
        cout << "0" << '\n';
        return 0;
    }
    long long ans = 0;
    add(arr[n - 1] + arr[n]);
    for (int j = n - 2; j >= 2; j--) {
        for (int i = 1; i < j; i++) {
            int cur = arr[i] + arr[j];
            int rem = t - cur;
            ans += sum(rem);
        }
        for (int k = j + 1; k <= n; k++) {
            add(arr[j] + arr[k]);
        }
    }
    cout << ans << '\n';
}