Submission #388447

#TimeUsernameProblemLanguageResultExecution timeMemory
388447JimmyZJXPacking Biscuits (IOI20_biscuits)C++14
9 / 100
1092 ms332 KiB
#include <iostream> #include <fstream> #include <algorithm> #include <cstring> #include <climits> #include <cassert> #include <tuple> #include <queue> #include <stack> #include <vector> #include <map> #include <set> #include <string> using namespace std; typedef long long LL; typedef vector<int> Vi; typedef vector<LL> VL; typedef vector<bool> Vb; typedef vector<vector<int>> Vii; #define MAXP 61 #define forR(i, n) for (int i = 0; i < (n); i++) VL preSum(MAXP); LL count(LL x, VL a, int p) { // [ 0, 2^p ) ++ [ 2^p , 2^(p+1) ) if (p == 0) { return a[0] >= x ? 2 : 1; } LL count_before_p = count(x, a, p - 1); if (a[p] >= x) { return 2 * count_before_p; } else if (p > 0 && a[p] + (preSum[p - 1] >> p) >= x) { LL rest = (x - a[p]) * (1LL << p); for (int c = p - 1; c >= 0 && rest > 0; c--) { LL cnt = min(a[c], rest / (1LL << c)); rest -= cnt * (1LL << c); a[c] -= cnt; } if (rest == 0) { // succeed return count_before_p + count(x, a, p - 1); } else { // failed return count_before_p; } } else { return count_before_p; } } LL count_tastiness(LL x, VL a) { int k = a.size(); a.resize(MAXP); forR(i, MAXP) { preSum[i] = i > 0 ? preSum[i - 1] : 0; preSum[i] += ((LL)1 << i) * a[i]; } return count(x, a, MAXP - 1); } #ifdef TEST_LOCAL int main() { LL res; res = count_tastiness(3, VL{ 5,2,1 }); res = count_tastiness(2, VL{ 2,1,2 }); return 0; } #endif

Compilation message (stderr)

biscuits.cpp: In function 'LL count_tastiness(LL, VL)':
biscuits.cpp:61:6: warning: unused variable 'k' [-Wunused-variable]
   61 |  int k = a.size();
      |      ^
#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...