Submission #538407

#	Time	Username	Problem	Language	Result	Execution time	Memory
538407		EqualTurtle	Packing Biscuits (IOI20_biscuits)	C++14	100 / 100	47 ms	1236 KiB

biscuits

#include "biscuits.h"
#include<bits/stdc++.h>
using namespace std;

constexpr long long MAXK = 63;

long long dp[MAXK];
long long sum[MAXK];
long long sx[MAXK];

long long logg(long long n){
	int curr = -1;
	while (n > 0){
		n = (n >> 1);
		curr++;
	}
	return curr;
}

long long foo(long long n)
{
	if (n <= 0)
		return 0;
	if (n == 1)
		return 1;
	
	long long l = logg(n);
	if (n == (1LL << l))
		l--;
	
	long long res = dp[l] + foo(min(n, 1 + sx[l]) - (1LL << l));
	return res;
}
 
long long count_tastiness(long long x, vector<long long> a)
{
	sum[0] = 0;
	for (long long i = 0; i < MAXK - 1; i++)
	{
		if (i < (long long)a.size())
			sum[i] += a[i] * (1LL << i);
		sx[i] = sum[i] / x;
		sum[i + 1] = sum[i];
	}
	
	for (long long i = 0; i < MAXK-1; i++)
		dp[i] = foo(1LL << i);

	//for (int i = 0; i < 4; i++)
	//	cout << sum[i] << " " << sx[i] << " " << dp[i] << "\n";
	return dp[MAXK - 2];
}

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