This code gets MLE but only uses, if I'm correct, three arrays of size n <= 2*10^5 for that problem: https://codeforces.net/contest/2038/problem/B.
Am I missing something?
I thought one long long was 8 Bytes and therefore 3*8*2*10^5 = 48*10^5 would be 4.8 MB?
Would love to be enlightened, thanks! Note that I'm not asking how to solve that problem, but rather why in the world I am getting MLE. Link to the MLE verdict: https://codeforces.net/contest/2038/submission/292217786
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
void solve() {
long long n;
cin >> n;
vector<long long> a(n), a_copy(n);
for (long long i = 0; i < n; i++) {
cin >> a[i];
}
auto is_feasible = [&](long long target) -> bool {
for (long long i = 0; i < n; i++) {
a_copy[i] = a[i];
}
bool first_time = true;
while (a_copy[0] > target || first_time) {
first_time = false;
for (long long i = 0; i < n; i++) {
long long a_i = a_copy[i];
if (a_i > target) {
long long excess = ((a_i - target) / 2) + ((a_i - target) % 2);
a_copy[i] -= 2 * excess;
long long nxt_idx = (i + 1) % n;
a_copy[nxt_idx] += excess;
}
}
}
return all_of(a_copy.begin(), a_copy.end(), [&](long long x) { return x == target; });
};
long long total_sum = accumulate(a.begin(), a.end(), 0LL);
vector<long long> targets;
for (long long i = 0; i <= total_sum / n; i++) {
targets.push_back(i * n);
}
long long l_ptr = -1, r_ptr = targets.size() - 1;
while (l_ptr < r_ptr) {
long long mid = (l_ptr + r_ptr + 1) / 2;
if (is_feasible(targets[mid] / n)) {
l_ptr = mid;
} else {
r_ptr = mid - 1;
}
}
if (r_ptr == -1) {
cout << -1 << endl;
return;
}
cout << total_sum - targets[l_ptr] << endl;
}
int main() {
long long n_tests;
cin >> n_tests;
for (long long test_nb = 0; test_nb < n_tests; test_nb++) {
solve();
}
return 0;
}
