이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
using int64 = long long;
using ld = long double;
constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e15 + 10;
constexpr int kMod = 1e9 + 7;
constexpr int kBits = 60;
void merge_biscuits(const int64 x, vector<int64> &biscuits) {
while (biscuits.size() <= kBits) biscuits.push_back(0);
for (int i = 0; i < kBits; i++) {
const int64 extra = max(0LL, biscuits[i] - x);
biscuits[i] -= extra;
biscuits[i + 1] += extra / 2;
}
}
int64 count_tastiness(int64 x, vector<int64> biscuits) {
merge_biscuits(x, biscuits);
map<pair<int64, int>, int64> memo;
memo[{0, kBits}] = 1;
function<int64(int64, int)> dp = [&](const int64 n, const int i) -> int64 {
if (memo[{n, i}] != 0) return memo[{n, i}];
if (biscuits[i] + n < x) return memo[{n, i}] = dp((biscuits[i] + n) / 2, i + 1);
return memo[{n, i}] = dp((biscuits[i] + n) / 2, i + 1) + dp((biscuits[i] + n - x) / 2, i + 1);
};
return dp(0, 0);
}
# | 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... |