제출 #1175547

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1175547		hyakup	Packing Biscuits (IOI20_biscuits)	C++20	0 / 100	395 ms	296636 KiB

biscuits

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

#define ll long long

const ll inf = 1e18 + 10;

ll count_tastiness( ll x, vector<ll> a ){
	int n = 61;
	while( (int)a.size() < n ) a.push_back(0);
	for( int i = 0; i < n; i++ ){
		if( a[i] >= x ){
			int aux = (a[i] - x)/2;
			a[i + 1] += aux;
			a[i] -= 2*aux;
		}
	}
	if( x >= 2e4 ) return 0;
	vector<vector<vector<ll>>> dp( n, vector<vector<ll>>( n, vector<ll>(x, -1)));
	//
	// cout << "a ";
	// for( int x : a ) cout << x << " ";
	// cout << endl;

	int max_shift = 0;
	for( int i = 0; i < n; i++ ){
		if( (x<<i) > inf ) break;
		max_shift = i;
	}

	function<ll( int, int, ll, ll )> solve = [&]( int i, int j, ll remain, ll num ){
		if( i < 0 ) return 1LL;
		if( dp[i][j][remain] != -1 ) return dp[i][j][remain];
		ll &resp = dp[i][j][remain];
		resp = solve( i - 1, j, remain, num);
		if( i >= max_shift ) return resp;
		ll goal = (x<<i);
		if( j > i ){ j = i; remain = a[i]; }
		if( (remain<<j) >= goal ){
			int qtd = (goal>>j);
			remain -= qtd;
			ll aux = solve( i - 1, j, remain, num + (1<<i) );

			// cout << "1 " << resp + aux << endl;
			return resp + aux;
		}
		goal -= (remain<<j);
		j--;
		while( j >= 0 ){
			if( (a[j]<<j) >= goal ){
				int qtd = (goal>>j);
				remain = a[j] - qtd;
				ll aux = solve( i - 1, j, remain, num + (1<<i) );
				// cout << "2 " << resp + aux << endl;
				return resp + aux;
			}
			goal -= (a[j]<<j);
			j--;
		}
		// cout << "3 " << resp << endl;
		return resp;
	};

	return solve( n - 1, n - 1, a[n - 1], 0 );
}

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