Submission #413159

#	Time	Username	Problem	Language	Result	Execution time	Memory
413159		atoiz	Packing Biscuits (IOI20_biscuits)	C++14	100 / 100	33 ms	1328 KiB

biscuits

#include "biscuits.h"
#include <numeric>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cassert>

using namespace std;

long long count_tastiness(long long x, vector<long long> a) {
	int k = (int) a.size();
	vector<long long> dp(k + 1);
	dp[0] = 1;
	for (int i = 0; i < k; ++i) {
		long long c = 0;
		for (int j = 0; j < i; ++j) c = (c + a[j]) / 2;
		c += a[i];
		
		if (c < x) {
			dp[i + 1] = dp[i];
			continue;
		}

		if (i < k - 1 && c >= 2 * x) {
			dp[i + 1] = dp[i] * 2;
			continue;
		}

		dp[i + 1] = dp[i] * (c / x - 1);
		
		auto b = a;
		b.resize(i + 1);	
		b.back() -= (c / x - 1) * x;

		while (true) {
			if (b.empty()) {
				++dp[i + 1];
				break;
			}

			long long d = 0;
			for (int j = 0; j < (int) b.size(); ++j) d = d / 2 + b[j];
			while (d >= 2 * x) { b.push_back(0); d /= 2; }
			
			dp[i + 1] += dp[b.size() - 1];

			if (b.back() >= x) {
				b.pop_back();
				continue;
			}

			long long rem = x;
			while (rem && !b.empty()) {
				if (b.back() <= rem) {
					rem -= b.back();
					b.pop_back();
				} else {
					b.back() -= rem, rem = 0;
				}
				rem *= 2;
			}
			if (rem) break;
		}
	}
	return dp[k];
}

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