Submission #1220834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220834		brinton	Packing Biscuits (IOI20_biscuits)	C++20	100 / 100	27 ms	948 KiB

biscuits

#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;
/*
key: all prefix is less than -> valid solution

*/
long long count_tastiness(long long x, vector<long long> a) {
	a.resize(60);
	vector<long long> sum(60,0);
	for(int i = 0;i < 60;i++){
		if(i > 0) sum[i] = sum[i-1];
		sum[i] += a[i]*(1LL << i);
	}

	vector<long long> limit(60);
	for(int i = 0;i < 60;i++){
		limit[i] = min((1LL<<(i+1))-1,sum[i]/x);
	}
	map<long long,long long> mp;
	mp[(1L << 60)-1] = 1;
	for(int i = 59;i >= 0;i--){
		map<long long,long long> nmp;
		for(auto &[rclim,rcnt]:mp){
			long long clim = rclim,cnt = rcnt;
			clim = min(clim,limit[i]);
			if(clim >= (1LL << i)){
				nmp[(1LL << i)-1] += cnt;
				clim -= (1LL << i);
			}
			nmp[clim] += cnt;
		}
		swap(mp,nmp);
	}

	long long tot = 0;
	for(auto [clim,cnt]:mp){
		tot += cnt;
	}
	return tot;
}

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