Submission #1188715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188715		hyakup	Packing Biscuits (IOI20_biscuits)	C++20	100 / 100	8 ms	1040 KiB

biscuits

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

#define ll long long

ll count_tastiness( ll x, vector<ll> a ){
	int n = 60;
	a.resize(n, 0LL);

	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);
	auto solve = [&]( int id, ll val ){
		ll ans = 1LL;
		for(val = min( val, sum[id]); id >= 0; val = min( val, sum[--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] + (( (sum[i]>>i) >= x ) ? solve(i - 1, sum[i] - (x<<i)) : 0 );


	return resp.back();
}

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