Submission #410466

#	Time	Username	Problem	Language	Result	Execution time	Memory
410466		534351	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	66 ms	1280 KiB

biscuits

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

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()

const int MAXN = 61;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int K;
ll X;
ll arr[MAXN], sum[MAXN];
map<ll, ll> dp[MAXN];

ll solve(int e, ll mx)
{
	ll c = sum[e], pw = (1ll << e);
	ckmin(mx, c);
	// cerr << "solve " << e << ' ' << mx << endl;
	if (e == 0)
	{
		return mx + 1;
	}
	if (dp[e].count(mx))
	{
		return dp[e][mx];
	}
	ll res = 0;
	if (mx >= pw)
	{
		res = solve(e - 1, pw - 1) + solve(e - 1, mx - pw);
	}
	else
	{
		res = solve(e - 1, mx);
	}
	dp[e][mx] = res;
	return res;
	//the part mod 2^e can be at most c.
}

ll count_tastiness(ll x, vl a)
{
	X = x;
	K = SZ(a);
	FOR(i, 0, K)
	{
		arr[i] = a[i];
	}
	FOR(i, 0, K)
	{
		sum[i] = arr[i] * (1ll << i) + (i == 0 ? 0 : sum[i - 1]);
	}
	while(sum[K - 1] / X >= (1ll << K))
	{
		sum[K] = sum[K - 1];
		K++;
	}
	FOR(i, 0, K)
	{
		sum[i] /= X;
		ckmin(sum[i], (2ll << i) - 1);
		dp[i].clear();
		// cerr << "sum " << sum[i] << endl;
	}
	return solve(K - 1, (1ll << K) - 1);
	//try to count numbers by their earliest violation?
}

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