Submission #1042580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042580		parsadox2	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	7 ms	1460 KiB

biscuits

#include "biscuits.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 130;
const long long inf = 3e18;
int n;
long long a[N] , reach[N] , dp[N] , x;

long long f(int id)
{
	if(id < 0)
		return 1;
	return dp[id];
}

long long solve(int id , long long bad = 0)
{
	//cout << id << " wtf: " << reach[id] << " " << bad << endl;
	if(id == -1)
		return 1;
	long long res = 0;
	if(reach[id] >= bad + x)
	{
		//cout << "MEOW " << endl;
		res += f(id - 1);
		bad += x;
	}
	res += solve(id - 1 , min(inf , 2LL * max(0LL , (bad - a[id]))));
	return res;
}

long long count_tastiness(long long xx, vector<long long> vec) {
	n = vec.size();
	x = xx;
	for(int i = 0 ; i < n ; i++)
		a[i] = vec[i];
	for(int i = n ; i < N ; i++)
		a[i] = 0;
	reach[0] = a[0];
	for(int i = 1 ; i < N ; i++)
		reach[i] = reach[i - 1] / 2 + a[i];
	long long ans = 0;
	for(int i = 0 ; i < N ; i++)
	{
		//cout << i << " ::: " << a[i] << " " << reach[i] << endl;
		if(reach[i] >= x)
			dp[i] = solve(i);
		else
			dp[i] = f(i - 1);
		//cout << i << " : " << dp[i] << endl;
	}
	return dp[N - 1];
}

Compilation message (stderr)

biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:44:12: warning: unused variable 'ans' [-Wunused-variable]
   44 |  long long ans = 0;
      |            ^~~

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