Submission #366205

#	Time	Username	Problem	Language	Result	Execution time	Memory
366205		dolphingarlic	Packing Biscuits (IOI20_biscuits)	C++14	100 / 100	95 ms	1004 KiB

biscuits

#include "biscuits.h"

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

ll x, s[60];
map<ll, ll> dp;

ll solve(ll n) {
	if (n <= 0) return 0;
	if (dp.count(n)) return dp[n];
	for (int i = 0; i < 60; i++) if ((1ll << i + 1) >= n)
		return dp[n] = solve(1ll << i) + solve(min(n, 1 + s[i] / x) - (1ll << i));
}

ll count_tastiness(ll x, vector<ll> a) {
	for (int i = 0; i < a.size(); i++) if (a[i] > x - 1) {
		ll to_merge = ((a[i] - x) >> 1) << 1;
			if (i == a.size() - 1) a.push_back(to_merge >> 1);
			else a[i + 1] += (to_merge >> 1);
		a[i] -= to_merge;
	}
	while (a.size() < 60) a.push_back(0);
	::x = x;
	memset(s, 0, sizeof s);
	s[0] = a[0];
	for (int i = 1; i < 60; i++)
		s[i] = s[i - 1] + (1ll << i) * a[i];
	dp.clear();
	dp[1] = 1;
	return solve(1ll << 60);
}

Compilation message (stderr)

biscuits.cpp: In function 'll solve(ll)':
biscuits.cpp:13:45: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   13 |  for (int i = 0; i < 60; i++) if ((1ll << i + 1) >= n)
      |                                           ~~^~~
biscuits.cpp: In function 'll count_tastiness(ll, std::vector<long long int>)':
biscuits.cpp:18:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for (int i = 0; i < a.size(); i++) if (a[i] > x - 1) {
      |                  ~~^~~~~~~~~~
biscuits.cpp:20:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |    if (i == a.size() - 1) a.push_back(to_merge >> 1);
      |        ~~^~~~~~~~~~~~~~~
biscuits.cpp: In function 'll solve(ll)':
biscuits.cpp:15:1: warning: control reaches end of non-void function [-Wreturn-type]
   15 | }
      | ^

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