Submission #419758

#	Time	Username	Problem	Language	Result	Execution time	Memory
419758		KoD	비스킷 담기 (IOI20_biscuits)	C++17	42 / 100	1089 ms	141196 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) {
	std::array<ll, 61> one{};
	one[60] = std::numeric_limits<ll>::max() / 2;
	for (int k = 59; k >= 50; --k) {
		one[k] = x - a[k];
		one[k] = std::min(one[k], one[k + 1] * 2 - a[k]);
		one[k] = std::max(one[k], 0ll);
	}
	std::array<HashTable<ll, ll>, 60> table{};
	a.resize(60);
	const auto dfs = RecLambda([&](auto&& dfs, const int k, const ll s) -> ll {
		if (k == 60) return 0;
		if (s < one[k]) return 0;
		if (table[k].find(s) != table[k].end()) {
			return table[k][s];
		}
		const auto t = s + a[k];
		ll ret = dfs(k + 1, t / 2);
		if (t >= x) {
			ret += dfs(k + 1, (t - x) / 2);
			ret += 1;
		}
		return table[k][s] = ret;
	});
	return dfs(0, 0) + 1;
}

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