Submission #520858

#	Time	Username	Problem	Language	Result	Execution time	Memory
520858		jamezzz	Packing Biscuits (IOI20_biscuits)	C++17	42 / 100	18 ms	11848 KiB

biscuits

#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll dp[65][100005];

ll count_tastiness(ll x,vector<ll> a){
	int k=a.size();
	ll t=0;
	for(int i=0;i<k;++i){
		t+=a[i]*(1ll<<i);
	}
	if(t<x)return 1;
	for(int i=0;i<k-1;++i){
		ll c=max(0ll,a[i]-x)/2;
		a[i]-=2*c;a[i+1]+=c;
	}
	for(int i=k-1;i>=0;--i){
		for(ll c=x;c>=0;--c){
			ll cur=c+a[i];
			if(i==k-1)dp[i][c]=cur/x+1;
			else{
				dp[i][c]=dp[i+1][cur/2];
				if(cur>=x)dp[i][c]+=dp[i+1][(cur-x)/2];
			}
		}
	}
	return dp[0][0];
}

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