# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
370080 | 2021-02-23T07:50:44 Z | MilosMilutinovic | Packing Biscuits (IOI20_biscuits) | C++14 | 0 ms | 0 KB |
#include "biscuits.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back const int N=62; ll x; map<ll, ll> dp; vector<ll> pref; ll Solve(ll n) { if(n<=0) return 0LL; if(n==1) return 1LL; if(dp.find(n)!=dp.end()) return dp[n]; ll i=__lg(n-1); ll ans=Solve((ll)(1<<i))+Solve(min(n,pref[i]/x+1)-(ll)(1<<i)); dp[n]=ans; return dp[n]; } ll count_tastiness(ll X, vector<ll> a) { x=X; dp.clear(); pref.clear(); for(ll i=0; i<(int)a.size(); ++i) { if(i>0) a[i]=a[i-1]+a[i]*(ll)(1<<i); pref.pb(a[i]); } for(int i=(int)ans.size(); i<61; ++i) pref.pb(pref.back()); return Solve(pref.back()+1); }