Submission #821718

#	Time	Username	Problem	Language	Result	Execution time	Memory
821718		oscar1f	Packing Biscuits (IOI20_biscuits)	C++17	42 / 100	1065 ms	44488 KiB

biscuits

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

using namespace std;
using ll=long long;

const ll MAX_VAL=61;
ll nbTas,ajout;
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);
	}
	memo[pos][rest-val[pos]]=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]<<" ";
	}
	for (ll i=0;i<MAX_VAL;i++) {
		if (val[i]>nbTas) {
			ajout=(val[i]-nbTas)/2;
			val[i]-=2*ajout;
			val[i+1]+=ajout;
		}
	}
	//cout<<endl;
	return dyna(0,0);
}

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