Problem Info
I’m doing this problem.
My Work
#include <iostream>
#include <cassert>
using std::cout;
using std::endl;
constexpr int MAX_SIZE = 5e3;
constexpr int MAX_MAG = 1e6;
int arr[MAX_SIZE];
int occ_num[2 * MAX_MAG + 1];
int pair_num[MAX_SIZE][MAX_SIZE - 1];
long long triple_num[MAX_SIZE][MAX_SIZE];
// 2020 jan gold
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(NULL);
freopen("threesum.in", "r", stdin);
int size;
int query_num;
std::cin >> size >> query_num;
assert(size <= MAX_SIZE);
for (int i = 0; i < size; i++) {
std::cin >> arr[i];
assert(-MAX_MAG <= arr[i] && arr[i] <= MAX_MAG);
}
for (int targ_ind = 2; targ_ind < size; targ_ind++) {
int target = -arr[targ_ind];
int curr_pairs = 0;
for (int i = targ_ind - 1; i >= 0; i--) {
if (abs(target - arr[i]) <= MAX_MAG) {
curr_pairs += occ_num[target - arr[i] + MAX_MAG];
}
pair_num[i][targ_ind - 1] = curr_pairs;
occ_num[arr[i] + MAX_MAG]++;
}
for (int i = targ_ind - 1; i >= 0; i--) {
occ_num[arr[i] + MAX_MAG]--;
}
}
for (int len = 3; len <= size; len++) {
for (int start = 0; start + len - 1 < size; start++) {
int end = start + len - 1;
triple_num[start][end] = (
triple_num[start][end - 1] + pair_num[start][end - 1]
);
}
}
freopen("threesum.out", "w", stdout);
for (int q = 0; q < query_num; q++) {
int start;
int end;
std::cin >> start >> end;
cout << triple_num[--start][--end] << '\n';
}
}
It’s slightly different from the official solution, but the core philosophy is still the same.
The thing is, even though the official solutions use the same amount of memory, my solution MLEs on the sample. Why is this the case?
