Submission #342176

#	Time	Username	Problem	Language	Result	Execution time	Memory
342176		chenwz	Packing Biscuits (IOI20_biscuits)	C++14	100 / 100	78 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, 1 + a.back());
}

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