Submission #645860

#	Time	Username	Problem	Language	Result	Execution time	Memory
645860		prvocislo	비스킷 담기 (IOI20_biscuits)	C++17	0 / 100	1069 ms	1388 KiB

biscuits

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
#include "biscuits.h"
typedef long long ll;
typedef long double ld;
using namespace std;

map<vector<ll>, ll> m;
ll rek(ll x, vector<ll> a)
{
	if (a.empty()) return 1;
	if (m.count(a)) return m[a];
	ll val = a.back();
	a.pop_back();
	ll ans = rek(x, a) * (val / x + 1);
	ll mis = x - (val % x);
	for (int i = (int)a.size() - 1; i >= 0; i--)
	{
		mis *= 2ll;
		ll k = min(a[i], mis);
		a[i] -= k;
		mis -= k;
		if (mis == 0)
		{
			while (a.size() > 1 && a[a.size() - 2] == 0) a.pop_back();
			ans += rek(x, a);
			break;
		}
	}
	return m[a] = ans;
}
ll count_tastiness(ll x, vector<ll> a) 
{
	m.clear();
	int n = a.size();
	for (int i = 0; i + 1 < n; i++)
	{
		ll k = (a[i] - x) / 2ll;
		a[i] -= 2 * k;
		a[i + 1] += k;
	}
	return rek(x, a);
}

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