Submission #411018

#	Time	Username	Problem	Language	Result	Execution time	Memory
411018		SeDunion	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	94 ms	972 KiB

biscuits

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

map<ll,ll>mp;

ll S[66];
int K;
ll x;

ll g(ll n) {
	if (n <= 1) return n == 1 ? 1 : 0;
	if (mp.count(n)) return mp[n];
	int i = 60;
	while ((1ll << i) >= n) --i;
	mp[n] = g(1ll << i) + g(min(n, 1 + S[i] / x) - (1ll << i));
	return mp[n];
}

ll count_tastiness(ll x_, vector<ll> a) {
	mp.clear();
	K = 62;
	while ((int)a.size() < K) a.push_back(0);
	x = x_;
	for (int i = 0 ; i < K ; ++ i) S[i] = 0;
	for (int i = 0 ; i < K ; ++ i) {
		for (int j = 0 ; j <= i ; ++ j) {
			S[i] += (1ll << j) * a[j];
		}
	}
	assert(S[K-1]<=(ll)1e18);
	return g(S[K-1]+1);
}

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