Submission #622374

#	Time	Username	Problem	Language	Result	Execution time	Memory
622374		8e7	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	16 ms	952 KiB

biscuits

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r){
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define lb ll
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#include "biscuits.h"

vector<lb> f, sum;

lb getcnt(lb v, int k) {
	if (v < 0) return 0;
	if (k < 0) return 1;
	if (v>>k) {
		return (k ? sum[k-1] : 1) + getcnt(min(v - ((v>>k)<<k), f[k]), k-1);
	} else {
		return getcnt(v, k-1);
	}
}
long long count_tastiness(long long x, std::vector<long long> a) {
	while (a.size() < 61) a.push_back(0);
	int k = a.size();
	for (int i = 0;i < k-1;i++) {
		ll d = max(0LL, ((a[i] - x)/2)*2);
		a[i] -= d;
		a[i+1] += d/2;
	}
	f.clear(), sum.clear();
	f.resize(k, 0);
	sum.resize(k, 0);
	
	for (int i = 0;i < k;i++) {
		lb tot = 0, se = 0;	
		for (int j = i-1;j >= 0;j--) {
			se <<= 1;
			se++;
			tot <<= 1;
			tot += a[j];
		}
		if (((tot + (((lb)a[i])<<i))>>i) < x)tot = -1;
		else tot = min(tot, tot + (((lb)(a[i] - x))<<i));
		if (tot < 0) tot = -1;
		else tot = tot / x;
		tot = min(tot, se);
		f[i] = tot;
	}
	//pary(f.begin(), f.end());
	
	for (int i = 0;i < k;i++) {
		sum[i] = (i ? sum[i-1] : 1) + getcnt(f[i], i-1);
	}
	return (long long)sum[k-1];
}
/*

1
1 40
1000

*/

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