Submission #421624

#	Time	Username	Problem	Language	Result	Execution time	Memory
421624		ja_kingy	비스킷 담기 (IOI20_biscuits)	C++14	100 / 100	27 ms	808 KiB

biscuits

#include "biscuits.h"

typedef long long ll;
ll min(ll a, ll b) {
	return a < b ? a : b;
}

ll count_tastiness(ll x, std::vector<ll> a) {
	a.resize(61);
	ll dp[61]{1};
	for (ll i = 1; i <= 60; ++i) {
		ll req = 0, mx = 1ll<<i;
		for (ll j = i-1; j >= 0; j--) {
			ll used = min(a[j],req/(1ll<<j)), rem = a[j]-used;
			req -= used * (1ll<<j);
			if (!req) {
				ll mxcnt = mx/(1ll<<j), blocks = rem/x, cnt =  min(mxcnt-1, blocks), extra = rem-x*blocks;
				dp[i] += dp[j] * (cnt+1);
				mx -= cnt*(1ll<<j);
				if (blocks < mxcnt-1 && (ll)1e18/x >= (1ll<<j)) {
					mx -= 1ll<<j;					
					req = (x-extra)*(1ll<<j);
				} else break;
			}
		}
	}
	return dp[60];
}

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