Submission #603957

#	Time	Username	Problem	Language	Result	Execution time	Memory
603957		Temmie	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	65 ms	1236 KiB

biscuits

#include <bits/stdc++.h>

long long count_tastiness(long long x, std::vector <long long> a) {
	std::vector <long long> tmp(61, 0);
	a.insert(a.end(), tmp.begin(), tmp.end());
	std::vector <long long> pre(61, 0);
	pre[0] = a[0];
	for (int i = 1; i <= 60; i++) {
		pre[i] = pre[i - 1] + a[i] * (1LL << i);
	}
	std::map <long long, long long> dp;
	auto f = [&] (auto&& self, long long val) -> long long {
		if (val < 0LL) {
			return 0;
		}
		if (!val) {
			return 1LL;
		}
		if (dp.count(val)) {
			return dp[val];
		}
		return dp[val] = self(self, (1LL << (63LL - __builtin_clzll(val))) - 1) + self(self, std::min(val, pre[63 - __builtin_clzll(val)] / x) - (1LL << (63LL - __builtin_clzll(val))));
	};
	return f(f, 1LL << 60);
}

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