This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define forint(i, N) for (long long i = 0; i < (N); i++)
using namespace std;
unordered_map<long long, long long> m;
long long count(long long x, vector<long long>& a, long long max_y) {
if (m[max_y] != 0) {
return m[max_y];
}
if (max_y == 0) {
m[0] = 1;
return 1;
}
if (max_y == 1) {
if (a[0] >= x) {
m[1] = 2;
return 2; // 0 & 1;
}
else {
m[1] = 1;
return 1; // 0 only
}
}
long long k = a.size();
vector<long long> sum(61, 0);
sum[0] = a[0];
for (long long i = 1; i < k; i++) {
sum[i] = sum[i - 1] + a[i] * (1ll << i);
}
for (long long i = k; i < 61; i++) {
sum[i] = sum[i-1];
}
long long i = 0;
while ((1ll << i) < max_y) {
i++;
}
if (max_y == (1ll << i)) {
if (sum[i] / x >= max_y) {
m[max_y] = count(x, a, max_y - 1) + 1;
return m[max_y];
}
else {
m[max_y] = count(x, a, max_y - 1);
return m[max_y];
}
}
long long aa = count(x, a, 1ll << (i-1));
if (sum[i-1] / (1ll << (i-1)) < x ) {
m[max_y] = aa;
return m[max_y];
}
else {
m[max_y] = aa + count(x, a, min(max_y - (1ll << (i-1)), sum[i-1]/x - (1ll << (i-1)))) - 1; // (1ll << (i-1)) double counted
return m[max_y];
}
}
long long count_tastiness(long long x, vector<long long> a) {
m.clear();
return count(x, a, 1e18);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |