Submission #436246

#	Time	Username	Problem	Language	Result	Execution time	Memory
436246		frodakcin	Packing Biscuits (IOI20_biscuits)	C++17	21 / 100	1082 ms	51940 KiB

biscuits

#include "biscuits.h"
#include <map>

using ll = long long;

const int MX = 200;

ll x;
std::map<ll, ll> map[MX];
std::vector<ll> a;

ll dfs(int d, ll v)
{
	if(d<(int)a.size()) v+=a[d];
	if(d>=(int)a.size() && v==0) return 1;

	auto it=map[d].find(v);
	if(it != map[d].end()) return it->second;

	ll ans = dfs(d+1, v/2);
	if(v>=x) ans += dfs(d+1, (v-x)/2);

	map[d].insert({v, ans});
	return ans;
}

long long count_tastiness(long long _x, std::vector<long long> _a)
{
	x=_x;
	a=_a;

	for(int i=0;i<MX;++i)
		map[i].clear();
	return dfs(0, 0);
}

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