Submission #620072

#	Time	Username	Problem	Language	Result	Execution time	Memory
620072		sofapuden	Packing Biscuits (IOI20_biscuits)	C++14	100 / 100	61 ms	1364 KiB

biscuits

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

using namespace std;

typedef long long ll;

map<ll,ll> dp;
ll A[61];
ll x;

ll f(ll n){
	if(n <= 0)return 0;
	if(n == 1)return 1;
	if(dp.find(n) != dp.end())return dp[n];
	ll a = __lg(n-1);
	return dp[n] = f(1ll<<a) + f(min(n,1+A[a]/x)-(1ll<<a));
}

ll count_tastiness(ll k, vector<ll> a) {
	x = k;
	dp.clear();
	while(a.size() <= 60)a.push_back(0);
	A[0] = a[0];
	for(int i = 1; i <= 60; ++i)A[i] = A[i-1] + (a[i]<<i);
	return f(A[60]+1);
}

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