Submission #1206974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206974		ansori	Packing Biscuits (IOI20_biscuits)	C++20	100 / 100	430 ms	968 KiB

biscuits

#include "biscuits.h"
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
map<ll , ll> mp;
ll f(ll x){
	if(x <= 0) return 1;
	ll c = 0;
	while(x){
		x /= 2;
		c ++;
	}
	return c;
}
ll get_ans(vector<ll> &a, ll x , ll lim){
	for(int i = 1;i <= 60; ++ i) lim = min(lim , a[f(lim / x) - 1]);
	if(lim < x) return (lim >= 0);
	if(mp.find(lim) != mp.end()) return mp[lim];
	ll p = f(lim / x) - 1;
	ll pw = (1ll << p);
	mp[lim] = (get_ans(a , x , (pw - 1) * x) + get_ans(a , x , min((pw - 1) * x , lim - pw * x)));
	return mp[lim];
}
long long count_tastiness(long long x, std::vector<long long> A) {
	mp.clear();
	int k = A.size();
	vector<ll> a(k);
	a[0] = A[0];
	for(ll i = 1;i < k; ++ i) a[i] = a[i - 1] + A[i] * (1ll << i);
	while(a.size() < 60) a.push_back(a.back());
	ll answ = get_ans(a , x , a.back());
	//for(auto to : mp) cout << to.fi << ' ' << to.se << '\n';
	return answ;
}

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