Submission #366209

#	Time	Username	Problem	Language	Result	Execution time	Memory
366209		dolphingarlic	Packing Biscuits (IOI20_biscuits)	C++14	100 / 100	78 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) {
	a.resize(60), ::x = x;
	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: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