제출 #558410

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
558410		ymm	Packing Biscuits (IOI20_biscuits)	C++17	77 / 100	1068 ms	1332 KiB

biscuits

///
///   Standing here
///   I realize
///   You are just like me
///   Trying to make history
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define Kill(x) exit((cout << (x) << '\n', 0))
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;

#ifndef LOCAL
#include "biscuits.h"
#else
ll count_tastiness(ll, vector<ll>);
int main()
{
	cout << count_tastiness(3, {5, 2, 1}) << '\n';
}
#endif


const int K = 63;
map<ll,ll> mm[K];
ll a[K];
ll x;

ll solve(int i, ll rem)
{
	if (i == K)
		return rem/x + 1;
	ll ans = 0;
	map<ll,ll>::iterator it1, it2;
	it2 = mm[i].lower_bound(rem);
	if (it2 == mm[i].end())
		goto solve_recurse;
	if (it2->first == rem)
		return it2->second;
	if (it2 == mm[i].begin())
		goto solve_recurse;
	it1 = it2; --it1;
	if (it1->second == it2->second)
		return it1->second;
solve_recurse:
	int r = 0;//rand()&1;
	if (r)
		ans += solve(i+1, (rem+a[i])/2);
	if (rem + a[i] >= x)
		ans += solve(i+1, (rem+a[i]-x)/2);
	if (!r)
		ans += solve(i+1, (rem+a[i])/2);
	mm[i][rem] = ans;
	return ans;
}

ll count_tastiness(ll _x, vector<ll> _a)
{
	x = _x; _a.resize(K);
	Loop (i,0,K) mm[i].clear();
	memset(a, 0, sizeof(a));
	Loop (i,0,K-1) {
		a[i] += _a[i];
		if (a[i] > x) {
			ll y = (a[i]-x)/2;
			a[i+1] += y;
			a[i] -= y*2;
		}
	}
	return solve(0, 0);
}

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