Submission #360151

#	Time	Username	Problem	Language	Result	Execution time	Memory
360151		juggernaut	Packing Biscuits (IOI20_biscuits)	C++14	42 / 100	149 ms	103788 KiB

biscuits

#include"biscuits.h"
#ifndef EVAL
#include"grader.cpp"
#endif
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[65][100005],x;
vector<ll>a;
ll rec(int pos,int cur){
	if(pos==61)return 1ll;
	if(~dp[pos][cur])return dp[pos][cur];
	dp[pos][cur]=rec(pos+1,(cur+a[pos])>>1ll);
	if(a[pos]+cur>=x)dp[pos][cur]+=rec(pos+1,(a[pos]+cur-x)>>1);
	return dp[pos][cur];
}
ll count_tastiness(ll X,vector<ll>A){
	a=A;x=X;
	a.resize(61);
	for(int i=0;i<60;i++)
		if(a[i]>x){
			ll tmp=(a[i]-x)>>1ll;
			a[i+1]+=tmp;
			a[i]-=(tmp<<1ll);
		}
	memset(dp,-1,sizeof dp);
	return rec(0,0);
}

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