Submission #1203858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203858		LucaLucaM	Packing Biscuits (IOI20_biscuits)	C++20	100 / 100	50 ms	1024 KiB

biscuits

#include "biscuits.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <map>

#define debug(x) #x << " = " << x << '\n'
using ll = long long;

ll count_tastiness(ll X, std::vector<ll> a) {
  while ((int) a.size() < 62) {
    a.push_back(0);
  }

  std::vector<ll> sum(62, 0);
  sum[0] = a[0];
  for (int i = 1; i < 62; i++) {
    sum[i] = sum[i - 1];
    sum[i] += (ll) (1LL << i) * a[i];
  }

  std::map<ll, ll> memo;

  auto calc = [&](auto &&self, ll n) {
    if (memo.count(n)) {
      return memo[n];
    }
    if (n <= 0) {
      return 0LL;
    }
    ll b = std::__lg(n - 1);
    return memo[n] = self(self, (1LL << b)) + self(self, std::min(n, 1 + sum[b] / X) - (1LL << b));
  };

  memo[0] = 0;
  memo[1] = 1;
  return calc(calc, (ll) 2e18);
}

/*

daca X <= 1e4 ce fac?
ma uit la primii 15 biti sau cv

daca incepand cu al 20lea bit iau ceva != 0 => 

*/

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