Submission #1067492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067492		Lalic	Packing Biscuits (IOI20_biscuits)	C++17	0 / 100	1062 ms	416 KiB

biscuits

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

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(). x.rend()
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> cd;

long long count_tastiness(long long x, vector<long long> a) {
	ll sum=0;
	for(ll i=0;i<(int)a.size();i++)
		sum+=(1ll<<i)*a[i];
	
	ll ans=1ll;
	for(ll curr=1ll;curr<=sum/x;curr++){
		set<pll> st; st.insert({x, curr});
		
		for(ll i=(int)a.size()-1;i>=0ll;i--){
			set<pll> novost;
			
			ll resto=a[i];
			for(auto u : st){
				if(!resto || u.se<(1ll<<i)){
					novost.insert(u);
					continue;
				}
				
				ll uso=min(resto, u.fi*(u.se/(1ll<<i)));
				resto-=uso;
				
				if(uso%(u.se/(1ll<<i))){
					novost.insert({uso/(u.se/(1ll<<i)), u.se%(1ll<<i)});
					novost.insert({1, u.se-((1ll<<i)*(uso%(u.se/(1ll<<i))))});
					if(u.fi-(uso/(u.se/(1ll<<i)))-1) novost.insert({u.fi-(uso/(u.se/(1ll<<i)))-1, u.se});
				}
				else{
					novost.insert({uso/(u.se/(1ll<<i)), u.se%(1ll<<i)});
					if(uso/(u.se/(1ll<<i))<u.fi) novost.insert({u.fi-(uso/(u.se/(1ll<<i))), u.se});
				}
			}
			
			st.clear();
			st=novost;
		}
		
		ll ok=1ll;
		for(auto u : st){
			//~ cout << u.fi << " " << u.se << "\n";
			if(u.se){
				ok=0;
				break;
			}
		}
		
		//~ if(ok) cout << "possible: " << curr << "\n";
		ans+=ok;
	}
	
	return ans;
}

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