Submission #730400

#TimeUsernameProblemLanguageResultExecution timeMemory
730400danikoynovPacking Biscuits (IOI20_biscuits)C++14
100 / 100
14 ms1336 KiB
#include "biscuits.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll maxk = 63; ll n, dp[maxk], b[maxk]; /*long long count_tastiness(long long x, vector<long long> a) { a.resize(20); n = a.size(); ll sum = 0; for (int i = 0; i < n; i ++) { sum += a[i] * ((ll)(1) << i); } ll ans = 0; for (ll d = 0; d <= sum; d ++) { for (int i = 0; i < 20; i ++) b[i] = a[i]; bool tf = true; for (ll bit = 0; bit < 20; bit ++) { ///cout << bit << " : " << b[bit] << endl; if ((d & (1 << bit)) > 0) { ///cout << "yes" << endl; if (b[bit] < x) { tf = false; break; } b[bit] -= x; } b[bit + 1] = b[bit + 1] + b[bit] / 2; } ///cout << d << " " << tf << endl; if (tf) ans ++; } ///cout << ans << endl; return ans; }*/ long long count_tastiness(long long x, vector<long long> a) { a.resize(maxk); n = a.size(); b[0] = a[0]; for (int i = 1; i < maxk; i ++) { b[i] = b[i - 1] / 2 + a[i]; } dp[0] = 1; if (a[0] >= x) dp[0] ++; for (ll i = 1; i < maxk; i ++) { dp[i] = 0; if (b[i] < x) { ///cout << "here " << i << " " << b[i] << " " << x << endl; dp[i] = dp[i - 1]; continue; } dp[i] = dp[i - 1]; ll nec = max((ll)(0), (x - a[i])) * 2; for (int j = i - 1; j >= 0; j --) { if (b[j] >= x + nec) { ///cout << i << " : " << j << endl; if (j == 0) dp[i] ++; else dp[i] = dp[i] + dp[j - 1]; ///cout << "here " << nec << " " << a[j] << endl; nec = max((ll)(0), (nec + x - a[j])) * 2; } else { ///cout << "bad " << i << " " << j << " " << nec << endl; nec = max((ll)(0), (nec - a[j])) * 2; } } dp[i] ++; } /**for (int j = 0; j < 7; j ++) cout << dp[j] << " "; cout << endl;*/ return dp[maxk - 1]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...