Submission #399079

#	Time	Username	Problem	Language	Result	Execution time	Memory
399079		Antekb	Packing Biscuits (IOI20_biscuits)	C++14	100 / 100	18 ms	1300 KiB

biscuits

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

const int K=62;
typedef long long ll;
ll ile[K], maks[K];
ll solve(ll r, int k, bool czy){//0<=r<(1<<k)
	if(czy && r>=maks[k])return ile[k];
	if(k==0)return (r==0);
	ll res=solve(min(r, 1ll<<(k-1)), k-1, 1);
	if(r>=(1ll<<(k-1)))res+=solve(r-(1ll<<(k-1)), k-1, 1);
	return res;
}
long long count_tastiness(long long x, std::vector<long long> a) {
	ll sum=0;
	a.resize(K);
	for(int i=0; i<K; i++){
		maks[i]=min((1ll<<i)-1, sum/x);
		ile[i]=solve(maks[i], i, 0);
		//cout<<i<<" "<<sum<<" "<<maks[i]<<" "<<ile[i]<<"\n";
		sum+=(a[i]<<i);
	}
	return ile[K-1];
}

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