Submission #303379

#	Time	Username	Problem	Language	Result	Execution time	Memory
303379		Namnamseo	Packing Biscuits (IOI20_biscuits)	C++17	77 / 100	1020 ms	1272 KiB

biscuits

#include <vector>
#include <map>
#include <algorithm>
#include <cstdio>
using namespace std;
using ll=long long;
using pll=pair<ll, ll>;

map<ll, ll> memo[100];
vector<ll> a;
ll k;
ll x;

ll F(int i, ll carry)
{
	if (i >= k) {
		return carry / x;
	}

	{
		auto ir = memo[i].lower_bound(carry);
		auto il = ir;
		if (il != memo[i].end() && il->first == carry) return il->second;
		if (il != memo[i].begin() && ir != memo[i].end()) {
			--il;
			if (il->second == ir->second) return il->second;
		}
	}

	ll &ret = memo[i][carry];

	ret = !!((a[i] + carry) / x);

	ret += F(i+1, (a[i] + carry) / 2);
	if (a[i] + carry >= x)
		ret += F(i+1, (a[i] + carry - x) / 2);

	return ret;
}

ll count_tastiness(ll x, vector<ll> a)
{
	::k = a.size();
	for(int i=0; i<64; ++i) memo[i].clear();
	::a = a;
	::x = x;
	return F(0, 0) + 1;
}

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