Submission #1320050

#TimeUsernameProblemLanguageResultExecution timeMemory
1320050nicolo_010Packing Biscuits (IOI20_biscuits)C++20
0 / 100
1095 ms332 KiB
#include <bits/stdc++.h>
#include "biscuits.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;

ll count_tastiness(ll x, vector<ll> a) {
	int k = a.size();
	ll sum=0;
	for (int i=0; i<k; i++) {
		sum += (1<<i)*a[i];
	}
	ll ans=0;
	for (int i=0; i<(sum+x-1)/x; i++)  {
		vector<ll> b = a; // O(k);
		bool can = true;
		for (int j=0; j<x; j++) {
			int s = i;
			for (int bm=k-1; bm>=0; bm--) {
				if (a[bm] && s>=(1<<bm)) {
					if (a[bm]*(1<<bm) <= s) {
						s -= a[bm]*(1<<bm);
						a[bm] = 0;
					}
					else {
						int cnt = s>>bm;
						s -= cnt*(1<<bm);
						a[bm]-=cnt;
					}
				} 
			}
			if (s>0) {
				can=false;
				break;
			}
		}
		if (can) {
			ans++;
		}
		swap(a, b); //O(1)
	}
	return ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...