# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1253946 | antonn | 비스킷 담기 (IOI20_biscuits) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
bool assign_min(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<typename T>
bool assign_max(T& a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
ll count_tastiness(ll x, vector<ll> a) {
while (a.size() < 62) {
a.push_back(0);
}
vector<ll> pref(62);
for (int i = 0; i < 62; i++) {
pref[i] = (i == 0 ? 0 : pref[i - 1]) + (a[i] << i);
}
map<ll, ll> f;
auto solve = [&](auto self, ll n) {
if (f.count(n)) {
return f[n];
}
if (n <= 0) {
return 0;
}
ll b = __lg(n - 1);
ll ans = self(self, (1LL << b)) + self(self, min(n, 1 + pref[b] / x) - (1LL << b));
return f[n] = ans;
};
f[0] = 0;
f[1] = 1;
return solve(solve, 1e18);
}