Submission #1071535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071535		jamjanek	Packing Biscuits (IOI20_biscuits)	C++14	100 / 100	10 ms	1472 KiB

biscuits

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

vector<long long>a,dp,pot;
long long x;
long long szukaj(long long val, int i){
	if(pot[i]*a[i]>=val){
		if(i==0)
			return 1;
		long long pom = val/pot[i];
		return dp[i-1] + szukaj((x-(a[i]-pom))*pot[i], i-1);
	}
	else{
		val-=pot[i]*a[i];
		if(i==0)
			return 0;
		return szukaj(val, i-1);
	}
}

long long count_tastiness(long long X, std::vector<long long> A) {
	int n = A.size(), i;
	x = X;
	for(i=0;i<n-1;i++){
		long long nadmiar = A[i]-x;
		if(nadmiar>0){
			if(nadmiar%2==0)
				A[i+1]+=nadmiar/2, A[i]=x;
			else
				A[i+1]+=nadmiar/2, A[i] = x+1;
		}
		
	}
	while(A.back()>0){
		long long nadmiar = A.back()-x;
		if(nadmiar>0){
			if(nadmiar%2==0)
				A.back()=x;
			else
				A.back()=x+1;
			A.push_back(nadmiar/2);
		}
		else
			A.push_back(0);
	}
	n = A.size();
	a = A;
	dp.clear();
	dp.resize(n);
	pot.clear();
	pot.resize(n);
	long long wynik = 1;
	for(i=0;i<n;i++){
		if(i==0)pot[0] = 1;
		else pot[i] = pot[i-1]*2;
		if(a[i]>=x){
			wynik*=2;
		}
		else{
			if((__int128)x*pot[i]>1000000000000000000 || i==0){
				dp[i] = wynik;
				continue;
			}
			wynik+=szukaj(pot[i]*(x-a[i]), i-1);
		}
		dp[i] = wynik;
	}
	return wynik;
}

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