Submission #1303562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303562		CSQ31	Packing Biscuits (IOI20_biscuits)	C++20	0 / 100	1109 ms	355968 KiB

biscuits

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

#define rep(i, a, b) for(int i=a; i<(b); ++i)
#define all(a) begin(a), end(a)
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define pb push_back

template<typename T> using v = vector<T>;
template<typename T> using vv = v<vector<T>>;

typedef long long ll;
typedef pair<int ,int > pii;
typedef v<int> vi;
//Represent y as a subset of indices
//yi = {0,x}
//a0 >= y0
//a1 + a0/2 >= y1 + y0/2
//a2 + a1/2 + a0 >= y2 + y1/2 + y0/4
//...
//mutiply the ith eqn by 2^i, we get
//a0 >= y0
//2a1 + a0 >= 2y1 + y0
//4a2 + 2a1 + a0 >= 4y2 + 2y1 + y0
//2^k*ak + .... + a0 >= 2^k*yk + ... y0

//Let S = set of possible values of y0+2y1+4y2 + ... 2^i * yi 
//after processing a0 to ai

//we need to do two things
//1) S = S U 2^i * x
//2) truncate S by p(i) = sum_j<=i 2^j * aj
//Obs: gap between segments <= 2^i, implying the number of segments is either 1 or 2
const ll INF = 2e18;
ll count_tastiness(ll x, vector<ll> a) {
	ll k = sz(a);
	vector<ll>p(60,0);
	for(int i=0;i<k;i++)p[i] = a[i]* (1LL<<i);
	for(int i=1;i<60;i++)p[i] += p[i-1];
	//for(ll x:p)cout<<x<<" ";
	//cout<<'\n';
	set<ll,greater<ll>>s;
	s.insert(0);
	for(int i=0;i<60;i++){
		if(x >= INF/(1LL<i)){}
		else{
			vector<ll>t;
			for(ll v:s){
				ll val = v + (1LL<<i)*x;
				if(val <= p[i])t.push_back(val);
			}
			for(ll v:t)s.insert(v);
		}
		while(!s.empty() && *s.begin() > p[i])s.erase(s.begin());
		//cout<<"At i\n";
		//for(ll x:s)cout<<x<<" ";cout<<'\n';
	}
	return sz(s);
}

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