Submission #342842

#	Time	Username	Problem	Language	Result	Execution time	Memory
342842		Register	Packing Biscuits (IOI20_biscuits)	C++14	35 / 100	29 ms	1388 KiB

biscuits

    #include "biscuits.h"
    #include <vector>
    #include <map>
    typedef long long LL;
    using namespace std;
    typedef vector<LL> VL;
    map<LL, LL> m;
    LL f(const VL& s, LL x, LL n) { // S(i) = ∑a(k)*(2^k)
      if (n <= 0) return 0;
      if (n == 1) return 1;
      if (m.count(n)) return m[n];
      LL i = __lg(n - 1), p2 = 1LL << i; // 2^i<n≤2^(i+1)
      return m[n] = f(s, x, p2) + f(s, x, min(n, 1 + s[i] / x) - p2);
    }
    LL count_tastiness(LL x, VL a) {
      m.clear();
      for (size_t i = 1; i < a.size(); i++) a[i] = a[i - 1] + (a[i] << i);
      while (a.size() <= 60) a.push_back(a.back());
      return f(a, x, a.back());
    }

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 21
• Subtask 4: 35 / 35
• Subtask 5: 0 / 23