Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "biscuits.h"
- #include <bits/stdc++.h>
- using namespace std;
- const int MX = 60;
- long long count_tastiness(long long x, vector<long long> a) {
- int k = a.size();
- long long maxSum = 0;
- for (int i = 0; i < k; ++i) {
- maxSum += (1LL << i) * a[i];
- }
- k = 1;
- long long p = 1;
- while (p < maxSum) ++k, p <<= 1;
- while (a.size() < k) a.push_back(0);
- auto possible = [&k, &a, &maxSum, &x](const bitset<MX> &y) {
- long long need = 0; // as a multiple of current power of two
- for (int i = k-1; i >= 0; --i) {
- if (y[i]) need += x;
- long long use = min(need, a[i]);
- need -= use;
- need <<= 1;
- if (need > maxSum) return false;
- }
- return !need;
- };
- bitset<MX> y = 0;
- long long ans = 1;
- bool foundNext = true;
- while (foundNext) {
- foundNext = false;
- bitset<MX> z = y;
- // find next highest y-value that works
- for (int i = 0; i < k; ++i) {
- if (y[i]) {z[i] = 0; continue;}
- // change a 0 into a 1, and set all smaller bits to 0
- z[i] = 1;
- if (possible(z)) {
- ++ans, y = z;
- foundNext = true;
- break;
- }
- z[i] = 0;
- }
- }
- return ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement