Submission #1240087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240087		franuch	Packing Biscuits (IOI20_biscuits)	C++20	100 / 100	38 ms	1040 KiB

biscuits

#include <bits/stdc++.h>
#include "biscuits.h"
using namespace std;
typedef long long ll;
typedef __int128 xl;
typedef pair<ll, ll> pll;
#define vc vector
#define st first
#define nd second
#define all(a) a.begin(), a.end()
#define sz(a) (ll)a.size()
#define pub push_back
#define pob pop_back

bool cont(xl mask, xl i) {
	return (mask & (xl(1) << i)) != 0;
}

xl two(xl i) {
	return xl(1) << i;
}

ll count_tastiness(ll _x, vc<ll> _a) {
	xl x = _x;
	vc<xl> a(all(_a));
	xl n = sz(a);
	vc<xl> dp(130);
	dp[0] = 1;
	vc<xl> mn(130);
	ll sa = 0;
	for (xl i = 1; ; i++) {
		if (i - 1 < n)
			sa += a[i - 1] * two(i - 1);
		mn[i] = sa / x;
	
		function<xl(xl, xl)> count = [&](xl i, xl b) {
			if (b < 0)
				return xl(0);
			if (i == 0)
				return xl(1);
			b = min(b, mn[i]);
			if (two(i - 1) <= b)
				return count(i - 1, b - two(i - 1)) + dp[i - 1];
			else
				return count(i - 1, b);
		};
		dp[i] = count(i, mn[i]);
		
		if (dp[i] == dp[i - 1] and i - 1 >= n)
			return dp[i];
	}
}

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