Submission #303874

#	Time	Username	Problem	Language	Result	Execution time	Memory
303874		ainta	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	70 ms	1024 KiB

biscuits

#include "biscuits.h"
#include<algorithm>
#include<map>
using namespace std;

long long S[61];

map<long long, long long>Map[61];

long long Go(int pv, long long M){
	M=min(M,S[pv]);
	M=min(M,2ll<<pv);
	if(Map[pv].count(M))return Map[pv][M];
	long long t = (1ll<<pv), s = 0;
	if(t <= M){
		if(pv==0) s++;
		else s += Go(pv-1,M-t);
	}
	if(pv==0)s++;
	else s += Go(pv-1,M);
	return Map[pv][M]=s;
}

long long count_tastiness(long long x, std::vector<long long> a) {
	int n = a.size();
	int i;
	for(i=0;i<=60;i++)Map[i].clear();
	for(i=0;i<n;i++){
		S[i] = (a[i]<<i);
		if(i)S[i]+=S[i-1];
	}
	for(i=n;i<=60;i++)S[i]=S[i-1];
	for(i=0;i<=60;i++)S[i]/=x;
	return Go(60,(1ll<<60));
}

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