제출 #1175582

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

biscuits

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

#define ll long long

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

ll dp[maxn][maxn][maxx];

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(0LL);
			ll aux = (a[i] - x)/2;
			a[i + 1] += aux;
			a[i] -= 2*aux;
		}
	}
	a.push_back(0);
	reverse(a.begin(), a.end() );
	a.push_back(0);
	reverse(a.begin(), a.end() );

	int n = a.size();
	if( x > 1 ) return 0;

	vector<ll> dp(n);
	dp[0] = 1LL;
	for( int i = 1; i < n; i++ ){
		int j = i - 1;
		int k = i - 1;
		while( a[j] == 1 ) j--;
		while( a[k] >= 1 ) k--;
		if( a[j] == 0 ) dp[i] = (1LL<<(i - j - 1))*dp[j];
		else dp[i] = dp[j] + dp[k]*(1LL<<(i - k - 1));
	}

	return dp.back();
	//
	//
	//
	//
	// for( int i = 0; i < n; i++ ) for( int j = 0; j < n; j++ ) for( int k = 0; k < x + 10; k++ ) dp[i][j][k] = -1;
	//
	//
	// 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 ){
	// 		ll qtd = (goal>>j);
	// 		remain -= qtd;
	// 		ll aux = solve( i - 1, j, remain, num + (1LL<<i) );
	//
	// 		// cout << "1 " << resp + aux << endl;
	// 		return resp + aux;
	// 	}
	// 	goal -= (remain<<j);
	// 	j--;
	// 	while( j >= 0 ){
	// 		if( (a[j]<<j) >= goal ){
	// 			ll qtd = (goal>>j);
	// 			remain = a[j] - qtd;
	// 			ll aux = solve( i - 1, j, remain, num + (1LL<<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: 12 / 12
• Subtask 3: 0 / 21
• Subtask 4: 0 / 35
• Subtask 5: 0 / 23