Submission #1280956

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280956		LaMatematica14	Packing Biscuits (IOI20_biscuits)	C++20	100 / 100	74 ms	976 KiB

biscuits

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

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

	map<pair<long long, int>, long long> m;
	function<long long(long long, int)> ric = [&](long long point, int lev) {
		if (lev == 1) {
			return min(ep[0], point)+1;
		}
		if (m.count({point, lev})) return m[{point, lev}];
		long long agg = 0;
		long long mprev = (1LL<<(lev-1))-1;
		agg += ric(min(point, mprev), lev-1);
		long long nex = min(point, ep[lev-1])-mprev-1; // check
		if (nex >= 0) agg += ric(nex, lev-1);
		m.insert({{point, lev}, agg});
		return agg;
	};

	return ric((1LL<<k)-1, k);
}

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