Submission #1070262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070262		Arapak	Packing Biscuits (IOI20_biscuits)	C++17	0 / 100	1 ms	348 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(x) begin(x), end(x)
#define sz(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

#ifdef DEBUG
auto& operator<<(auto &os, const pair<auto,auto> &p) {
	return os<<"("<<p.first<<", "<<p.second<<")";
}
auto& operator<<(auto &os, const auto &v) {
	os<<"{";
	for(auto it=begin(v);it!=end(v);++it) {
		if(it != begin(v)) os<<", ";
		os<<(*it);
	}
	return os<<"}";
}

void dbg_out(auto... x) {
	((cerr<<' '<<x), ...) << endl;
}
#define dbg(x...) cerr<<"("<<#x<<"):", dbg_out(x);
#else
#define dbg(...)
#endif
typedef vector<ll> vll;

const ll inf = ll(1e18) + 7;

ll k;

// ll num(ll val, vll a) {
// 	if(val == 0) return inf;
// 	if(val >= (1LL<<k)) return 0;
// 	vll needed(k, 0);
// 	rep(i,0,k)
// 		if((val>>ll(i)) & 1LL)
// 			needed[i] = 1;
// 	ll result = 0;
// 	while(true) {
// 		int mini = -1;
// 		rep(i,0,k) {
// 			if(needed[i] == 0) continue;
// 			if(mini == -1 || (a[i] / needed[i]) < (a[mini] / needed[mini]))
// 				mini = i;
// 		}
// 		if(mini == -1) break;
// 		ll res = a[mini] / needed[mini];
// 		result += res;
// 		if(mini == 0) break;
// 		rep(i,0,k) a[i] -= res * needed[i];
// 		needed[mini-1] += needed[mini] * 2;
// 		needed[mini] = 0;
// 	}
// 	return result;
// }

vll a;
map<pair<ll,ll>, ll> m;

ll solve(ll bit, ll added) {
	dbg(bit, added);
	if(bit >= 61) return 1;
	if(m.count({bit, added}))
		return m[{bit, added}];
	ll res = 0;
	ll val = (bit >= k ? 0 : a[bit]) + added;
	res += solve(bit+1, val / 2);
	if(val > 0) res += solve(bit+1, (val-1) / 2);
	return m[{bit,added}] = res;
}

ll count_tastiness(ll x, vll A) {
	a = A;
	dbg(a);
	k = sz(a);
	ll res = solve(0, 0);
	dbg(m);
	return res;
	// ll res = 0;
	// rep(i,0,100007) {
	// 	bool poss = num(i, a) >= x;
	// 	if(poss) dbg(i);
	// 	res += poss;
	// }
	// return res;
}

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