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>
//#include <unordered_map>
#define forint(i, N) for (long long i = 0; i < (N); i++)
using namespace std;
typedef long long ll;
vector<ll> sum(61, 0);
unordered_map<ll, ll> m;
long long count(long long x, vector<long long>& a, ll max_y) {
// returns how many y <= max_y that are OK
//cerr << "hello - " << max_y << endl;
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;
}
else {
m[1] = 1;
return 1;
}
}
int i = 0;
while ((1ll << i) < max_y) {
i++;
//cerr << max_y << " ja " << (1ll <<i) << endl;
}
//(2^(i-1) < max_y << (2^i)
if (max_y == (1ll << i)) {
if (max_y <= sum[i] / x) {
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];
}
}
if (sum[i-1]/x < (1ll << (i - 1))) {
m[max_y] = count(x, a, (1ll << (i - 1)));
return m[max_y];
}
// ((1 << (i - 1)) + y) * x < s[i-1]
// ((1 << (i - 1)) + y) < s[i-1]/x
// y < s[i-1]/x - (1 << (i - 1))
ll min_v = min(max_y - (1ll << (i - 1)), sum[i-1]/x - (1ll << (i - 1)));
m[max_y] = count(x, a, (1ll << (i - 1))) + count(x, a, min_v) - 1;
return m[max_y];
}
long long count_tastiness(long long x, vector<long long> a) {
int k = a.size();
sum[0] = a[0];
for (int i = 1; i < k; i++) {
sum[i] = sum[i - 1] + (a[i] << i);
}
for (int i = k; i < sum.size(); i++) {
sum[i] = sum[i - 1];
}
return count(x, a, (ll)1e18);
}
Compilation message (stderr)
biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:79:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for (int i = k; i < sum.size(); i++) {
| ~~^~~~~~~~~~~~
# | 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... |