Submission #1234110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234110		madamadam3	Packing Biscuits (IOI20_biscuits)	C++20	0 / 100	13 ms	328 KiB

biscuits

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

using namespace std;

#ifdef LOCAL
	#define dbg(x) (cout << (x))
#else
	#define dbg(x)
#endif

typedef long long ll;
using vi =vector<int>;
using vl = vector<ll>;
#define pb push_back
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define trace(x) for (auto &el : x) {dbg(el); dbg(" ");}

ll count_tastiness(ll x, vl a) {
	ll k = a.size();
	const ll BITS = 31;
	ll SUM = 0;
	for (ll i = 0; i < k; i++) SUM += a[i] * (1 << i);
	SUM /= x;

	a.resize(max(k, BITS));
	trace(a); dbg("\n");

	// dbg("x: "); dbg(x); dbg(" k: "); dbg(k); dbg("\n");

	vl DP(BITS+1, 0);
	DP[0] = 1;

	for (ll i = 0; i < BITS; i++) {
		ll mysum = DP[i];
		if (a[i] >= x) {
			mysum *= 2;
		} else {
			int best = -1;
			for (int bg = 0; bg < i; bg++) {
				vl tmpa(a.begin(), a.end());
				for (int en = bg; en < i; en++) {
					tmpa[en+1] += tmpa[en] / 2;
					tmpa[en] -= (tmpa[en] / 2) * 2;
				}
				if (tmpa[i] >= x) {
					best = bg;
				}
			}
			if (best != -1) mysum += DP[best];
		}

		DP[i+1] = mysum;
		ll remainder = max(0LL, a[i] - x);
		ll to_give = remainder / 2;
		if (i < BITS - 1) a[i+1] += to_give;
		a[i] -= to_give * 2;
	}

	return DP[BITS];
}

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