# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
389900 | 2021-04-14T20:30:01 Z | Osama_Alkhodairy | Packing Biscuits (IOI20_biscuits) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h> //~ #include "biscuits.h" #include "grader.cpp" using namespace std; #define ll long long int k; ll x; vector <ll> a, s; map <ll, ll> dp; ll solve(ll p){ if(p == 1) return 1; if(p <= 0) return 0; if(dp.count(p)) return dp[p]; int b = __lg(p); if((p & (p - 1)) == 0) b--; return dp[p] = solve(1LL << b) + solve(min(p, 1 + s[b] / x) - (1LL << b)); } long long count_tastiness(long long X, vector<long long> A){ x = X; a = A; k = a.size(); while(k < 60){ a.push_back(0); k++; } s.clear(); s.resize(k); for(int i = 0 ; i < k ; i++){ if(i > 0) s[i] = s[i - 1]; s[i] += (1LL << i) * a[i]; } dp.clear(); return solve(1LL << 60); }