# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1206013 | bangan | Packing Biscuits (IOI20_biscuits) | C++20 | 0 ms | 0 KiB |
#include "biscuits.h"
#include <bits/stdc++.h>
using i64 = long long;
long long count_tastiness(long long x, std::vector<long long> a) {
for (int i = 0; i < a.size(); i++) {
if (a[i] > x + 1 && i + 1 == k.size()) {
a.push_back(0);
}
if (a[i] > x + 1) {
i64 t = (a[i] - x) / 2;
a[i] -= 2 * t;
a[i + 1] += t;
}
}
int k = a.size();
std::map<std::pair<int, i64>, i64> save;
auto f = [&](auto self, int i, i64 n) -> i64 {
if (save.find(std::make_pair(i, n)) != save.end()) {
return save[std::make_pair(i, n)];
}
i64 cur = n;
if (i < k) {
cur += a[i];
}
if (cur == 0) {
return 1;
}
i64 res = self(self, i + 1, cur / 2);
if (cur >= x) {
res += self(self, i + 1, (cur - x) / 2);
}
return save[std::make_pair(i, n)] = res;
};
return f(f, 0, 0);
}