Submission #342840

#	Time	Username	Problem	Language	Result	Execution time	Memory
342840		Register	Packing Biscuits (IOI20_biscuits)	C++14	0 / 100	5 ms	384 KiB

biscuits

//test
#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, 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: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 21
• Subtask 4: 0 / 35
• Subtask 5: 0 / 23