제출 #558402

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
558402		ymm	Packing Biscuits (IOI20_biscuits)	C++17	42 / 100	1087 ms	5332 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, X = 10010;
ll mm[K][X], a[K];
ll x;

ll solve(int i, ll rem)
{
	if (i == K)
		return rem/x + 1;
	if (x <= 10000 && mm[i][rem] != -1)
		return mm[i][rem];
	ll ans = solve(i+1, (rem+a[i])/2);
	if (rem + a[i] >= x)
		ans += solve(i+1, (rem+a[i]-x)/2);
	if (x <= 10000)
		mm[i][rem] = ans;
	return ans;
}

ll count_tastiness(ll _x, vector<ll> _a)
{
	x = _x; _a.resize(K);
	memset(mm, -1, sizeof(mm));
	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: 0 / 35
• Subtask 5: 0 / 23