Submission #1240343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240343		AMnu	Packing Biscuits (IOI20_biscuits)	C++20	100 / 100	9 ms	948 KiB

biscuits

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

const int LOG = 61;
const ll l = 1;

ll dp[LOG], mx[LOG], sum, m;

ll count_tastiness(ll x,vector<ll> a) {
	dp[0] = 1;
	sum = a[0];
	for (int i=1;i<LOG;i++) {
		mx[i] = sum / x;
		if (i < (int)a.size()) {
			sum += a[i]<<i;
		}
		if (mx[i] >= (l<<i)) {
			dp[i] = 2*dp[i-1];
			continue;
		}
		dp[i] = 1;
		m = mx[i];
		for (int j=i-1;j>=0;j--) {
			if ((m>>j)&l) {
				dp[i] += dp[j];
				m ^= l<<j;
			}
			m = min(m, mx[j]);
		}
	}
	return dp[LOG-1];
}

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