Submission #356837

#	Time	Username	Problem	Language	Result	Execution time	Memory
356837		Kerim	Packing Biscuits (IOI20_biscuits)	C++17	42 / 100	1100 ms	14944 KiB

biscuits

#include "biscuits.h"
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
ll X,odp[61];
unordered_map<ll,ll>dp[61];
vector<ll>a;
bool bad(int pos,ll cur){
	if(odp[pos]<=cur)return 0;
	while(pos<61){
		if(cur+a[pos]>=X){
			odp[pos]=cur;
			return 0;
		}
		cur=(cur+a[pos++])/2;	
	}return 1;
}
ll rec(int pos,ll cur){
	assert(cur<2*X);
	if(bad(pos,cur))return 1;
	if(pos==61)return 1;
	if(dp[pos].find(cur)!=dp[pos].end())return dp[pos][cur];
	ll ret=rec(pos+1,(cur+a[pos])/2);
	if(a[pos]+cur>=X)ret+=rec(pos+1,(a[pos]+cur-X)/2);
	return dp[pos][cur]=ret;
}
long long count_tastiness(long long x, vector<long long> A) {
	X=x;a=A;
	for(int i=0;i<61;i++)odp[i]=2*X,dp[i].clear();
	while(int(a.size())<61)a.pb(0);
	for(int i=0;i<60;i++)
		if(a[i]>x){
			ll tmp=(a[i]-x)/2;
			a[i+1]+=tmp;
			a[i]-=tmp<<1;	
		}
	return rec(0,0);
}

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