Submission #1203855

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203855		LucaLucaM	Packing Biscuits (IOI20_biscuits)	C++20	9 / 100	15 ms	912 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;
using i128 = __int128;

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

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

  std::map<i128, i128> memo;

  auto calc = [&](auto &&self, ll n) {
    if (memo.count(n)) {
      return memo[n];
    }
    if (n <= 0) {
      return (i128) 0;
    }
    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[1] = 1;
  return calc(calc, 8e18);
}

/*

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