Submission #1042578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042578		parsadox2	Packing Biscuits (IOI20_biscuits)	C++17	0 / 100	1 ms	348 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)
		res += f(id - 1);
	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++)
	{
		dp[i] = f(i - 1);
		if(reach[i] >= x)
		{
			if(a[i] >= x)
				dp[i] += f(i - 1);
			else
				dp[i] += solve(i - 1 , 2 * (x - a[i]));
		}
		//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:40:12: warning: unused variable 'ans' [-Wunused-variable]
   40 |  long long ans = 0;
      |            ^~~

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