Submission #1054873

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054873		Gromp15	Packing Biscuits (IOI20_biscuits)	C++17	42 / 100	339 ms	1628 KiB

biscuits

#include <bits/stdc++.h>
#include "biscuits.h"
#define ll long long
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using namespace std;

long long count_tastiness(long long x, std::vector<long long> a) {
	if (x <= 10001) {
		map<ll, ll> dp;
		dp[0] = 1;
		for (int i = 0; i < sz(a) + 100; i++) {
			map<ll, ll> dp2;
			ll cur = i < sz(a) ? a[i] : 0;
			for (auto [j, val] : dp) {
				if (j + cur >= x) dp2[(j + cur - x) >> 1] += val;
				dp2[(j + cur) >> 1] += val;
			}
			swap(dp, dp2);
		}
		ll ans = 0;
		for (auto [z, y] : dp) ans += y;
		return ans;
	}
	int ans = 0;
	auto solve = [&](auto&& s, vector<ll> left, int idx) -> void {
		if (idx == -1) {
			ans++; return;
		}
		s(s, left, idx - 1);
		ll cur = x;
		for (int i = idx; i >= 0; i--) {
			if (cur > 4e18) break;
			ll req = min(cur, left[i]);
			cur -= req, left[i] -= req;
			if (cur == 0) {
				s(s, left, min(i, idx - 1));
				break;
			}
			cur *= 2;
		}
	};
	solve(solve, a, sz(a) - 1);
	return ans;
}

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