Submission #821708

#	Time	Username	Problem	Language	Result	Execution time	Memory
821708		oscar1f	Packing Biscuits (IOI20_biscuits)	C++17	0 / 100	1084 ms	49744 KiB

biscuits

#include<bits/stdc++.h>
#include "biscuits.h"

using namespace std;
using ll=long long;

const ll MAX_VAL=61;
ll nbTas;
ll val[MAX_VAL];
unordered_map<ll,ll> memo[MAX_VAL];

ll dyna(ll pos,ll rest) {
	if (pos==MAX_VAL) {
		return 1;
	}
	if (memo[pos][rest]!=0) {
		return memo[pos][rest];
	}
	ll ans=0;
	rest+=val[pos];
	ans+=dyna(pos+1,rest/2);
	if (rest>=nbTas) {
		ans+=dyna(pos+1,(rest-nbTas)/2);
	}
	if (memo[pos][rest]!=0 and memo[pos][rest]!=ans) {
		exit(1);
	}
	memo[pos][rest]=ans;
	return ans;
}

ll count_tastiness(ll x,vector<long long> a) {
	nbTas=x;
	for (ll i=0;i<MAX_VAL;i++) {
		memo[i].clear();
		if (i>=(ll)a.size()) {
			val[i]=0;
		}
		else {
			val[i]=a[i];
		}
		//cout<<val[i]<<" ";
	}
	//cout<<endl;
	return dyna(0,0);
}

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