Submission #1188710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188710		hyakup	Packing Biscuits (IOI20_biscuits)	C++20	0 / 100	7 ms	912 KiB

biscuits

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

#define bug(x) cout << #x << " " << x << endl;

#define ll long long

const ll inf = 1e18 + 10;
const int maxn = 61;
const int maxx = 2e4;


ll count_tastiness( ll x, vector<ll> a ){

	for( int i = 0; i < (int)a.size(); i++ ) if( a[i] > x ){
		if( i == (int)a.size() - 1 ) a.push_back(0);
		ll aux = (a[i] - x)/2;
		a[i + 1] += aux;
		a[i] -= 2*aux;
	}

	int n = a.size();

	vector<ll> sum( n, a[0] );
	for( int i = 1; i < n; i++ ) sum[i] = sum[i - 1] + (a[i]<<i);

	vector<ll> resp(n + 1, 1);
	function<ll(int, ll)> solve = [&]( int id, ll val ){
		ll ans = 1;
		for(; id >= 0; id-- )
			if( (val>>id) >= x ) ans += resp[id], val -= (x<<id);
		return ans;
	};

	// resp[i + 1] corresponde ao bit i
	for( int i = 0; i < n; i++ ){
		resp[i + 1] = resp[i];
		if( (sum[i]>>i) < x ) continue;

		resp[i + 1] += solve( i - 1, sum[i] - (x<<i) );
	}

	return resp.back();
}

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