Submission #833558

#	Time	Username	Problem	Language	Result	Execution time	Memory
833558		Sohsoh84	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	12 ms	1292 KiB

biscuits

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

using namespace std;

typedef long long ll;

#define sep			' '
#define debug(x)		cerr << #x << ": " << x << endl;

const int MAXN = 61; // TODO

inline bool ovf_mul(ll a, ll b) {
	ll mx = numeric_limits<ll>::max();
	return b > mx / a;
}

ll A[MAXN], dp[MAXN], ps[MAXN], x;

inline ll f(ll i, ll mask) {
	if (i == 0) return (mask == 0 ? 1 : dp[i]);
	if (mask >= (1ll << (i + 1))) return dp[i];
	if (!(mask >> i & 1ll)) return f(i - 1, mask);
	
	ll tmask = mask ^ (1ll << i);
	if (A[i] >= x) return f(i - 1, tmask) + dp[i - 1];
	ll fmask = ps[i] / x - (1ll << i);
	if (fmask < 0) return dp[i - 1];

	return dp[i - 1] + f(i - 1, min(fmask, tmask));
}

ll count_tastiness (ll x_, vector<ll> a_) {
	x = x_;
	memset(A, 0, sizeof A);
	memset(dp, 0, sizeof dp);
	memset(ps, 0, sizeof ps);

	for (int i = 0; i < int(a_.size()); i++) {
		A[i] = a_[i];
		ps[i] = (A[i] << i);
	}
	
	dp[0] = (A[0] >= x ? 2 : 1);
	for (int i = 1; i < MAXN; i++) {
		ps[i] += ps[i - 1];
		dp[i] = dp[i - 1];
		
		ll m = ps[i] / x - (1ll << i);
		if (m >= 0) dp[i] += f(i - 1, m);

	}

	return dp[MAXN - 1];
}

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