제출 #421511

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
421511		KoD	비스킷 담기 (IOI20_biscuits)	C++17	100 / 100	136 ms	1336 KiB

biscuits

#include <bits/extc++.h>
#include "biscuits.h"

namespace {

using ll = long long;
template <class T> using Vec = std::vector<T>;
template <class T, class U> using HashTable = __gnu_pbds::gp_hash_table<T, U>;

template <class F> struct RecLambda: private F {
	explicit RecLambda(F&& f): F(std::forward<F>(f)) {}
	template <class... Args> decltype(auto) operator() (Args&&... args) const {
		return F::operator()(*this, std::forward<Args>(args)...);
	}	
};

}

ll count_tastiness(ll x, Vec<ll> a) {
	a.resize(60);
	std::array<ll, 60> sum{};
	for (int i = 0; i < 60; ++i) {
		sum[i] = (i == 0 ? 0 : sum[i - 1]) + (a[i] << i);
	}
	HashTable<ll, ll> table;
	table[1] = 1;
	return RecLambda([&](auto&& dfs, const ll n) -> ll {
		if (n <= 0)  {
			return 0;
		}
		if (table[n] != 0) {
			return table[n];
		}
		int logn = 0;
		while (((ll) 1 << (logn + 1)) < n) {
			logn += 1;
		}
		return table[n] = dfs((ll) 1 << logn) + dfs(std::min(sum[logn] / x + 1, n) - ((ll) 1 << logn));
	})((ll) 1 << 60);
}

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