Submission #522284

#	Time	Username	Problem	Language	Result	Execution time	Memory
522284		jamezzz	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	35 ms	1316 KiB

biscuits

#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int k;
ll x;
vector<ll> s;
unordered_map<ll,ll> m;

int lg2(ll x){
	int l=0,h=60,m,r=1;
	while(l<=h){
		m=(l+h)/2;
		if((1ll<<m)<x)r=m,l=m+1;
		else h=m-1;
	}
	return r;
}

ll dp(ll n){
	if(n<=0)return 0;
	if(n==1)return 1;
	if(m[n]!=0)return m[n];
	int i=lg2(n);
	return m[n]=dp(1ll<<i)+dp(min(n,1+s[i]/x)-(1ll<<i));
}

ll count_tastiness(ll _x,vector<ll> a){
	s.resize(60);
	x=_x;
	while((int)a.size()<60)a.push_back(0);
	for(int i=0;i<60;++i){
		s[i]=a[i]*(1ll<<i);
		if(i!=0)s[i]+=s[i-1];
	}
	m.clear();
	return dp((1ll<<60));
}

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