Submission #645904

#	Time	Username	Problem	Language	Result	Execution time	Memory
645904		prvocislo	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	423 ms	1432 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;

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

Compilation message (stderr)

biscuits.cpp: In function 'll rek(ll, std::vector<long long int>)':
biscuits.cpp:29:34: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |  ans = rek(x, a) * (a.size() + 1 == n ? (val / x + 1) : min(2ll, val / x + 1));
      |                     ~~~~~~~~~~~~~^~~~
biscuits.cpp:30:30: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |  if (val < x || a.size() + 1 == n)
      |                 ~~~~~~~~~~~~~^~~~

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