| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 335527 | aanastasov | Packing Biscuits (IOI20_biscuits) | C++17 | 0 ms | 0 KiB |
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 "biscuits.h"
#include <cassert>
int64_t count_tastiness(int64_t x, std::vector<int64_t> a) {
while (a.size() < 62) a.push_back(0);
int64_t extra = 0;
auto ways = std::vector<int64_t>{1};
for (int64_t i = 0; i < a.size(); ++i) {
if (a[i] + (extra >> i) >= x) {
extra += (1LL << i) * a[i];
extra -= (1LL << i) * x;
assert(extra >= 0);
ways.push_back(ways.back() * 2);
} else {
auto counts = std::vector<int64_t>(a.begin(), a.end());
int64_t upper_bound = 0;
for (int64_t j = i; j >= 0; --j) {
int64_t available = 0;
for (int64_t jj = 0; jj < j + 1; ++jj)
available += counts[jj] * (1LL << jj);
if ((available >> j) < x)
continue;
int64_t needed = x;
for (int64_t jj = j; jj >= 0; --jj) {
int64_t am = std::min(needed, counts[jj]);
counts[jj] -= am;
needed = (needed - am) * 2;
}
upper_bound |= 1LL << j;
}
int64_t res = 0;
upper_bound++;
for (int64_t j = 0; j < i + 1; ++j)
if ((upper_bound & (1LL << j)) > 0)
res += ways[j];
ways.push_back(res);
extra = 0;
}
}
return ways.back();
}