Submission #306038

#	Time	Username	Problem	Language	Result	Execution time	Memory
306038		Yousef_Salama	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	88 ms	1016 KiB

biscuits

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

long long count_tastiness(long long x, vector <long long> a){
	a.resize(60, 0);
	const int k = 60;
	
	vector <long long> p2(k);
	
	p2[0] = 1;
	for(int i = 1; i < k; i++)
		p2[i] = p2[i - 1] * 2;
	
	vector < vector <long long> > b(k, vector <long long>(k));
	for(int i = 0; i < k; i++){
		long long total = 0;
		for(int j = 0; j <= i; j++)
			total += p2[j] * a[j];
			
		for(int j = i; j >= 0; j--){
			if(total / p2[j] >= x){
				b[k - i - 1][k - j - 1] = 1;
				total -= p2[j] * x;
			}else{
				b[k - i - 1][k - j - 1] = 0;
			}
		}
	}
	
	/*
	for(int i = 0; i < k; i++){
		for(int j = 0; j < k; j++)
			cout << b[i][j] << ' ';
		cout << endl;
	}
	*/
	
	auto cmp = [&](int i, int j){
					for(int l = max(i, j); l < k; l++){
						if(b[i][l] < b[j][l]){
							return true;
						}else if(b[i][l] > b[j][l]){
							return false;
						}
					}
					return false;
				};
	
	vector < vector <long long> > dp(k, vector <long long>(k));
	
	for(int i = k - 1; i >= 0; i--)
	for(int j = 0; j <= i; j++){
		if(i == k - 1){
			if(b[j][i] == 1)dp[i][j] = 2;
			else dp[i][j] = 1;
		}else{
			if(cmp(j, i + 1))dp[i][j] = dp[i + 1][j];
			else dp[i][j] = dp[i + 1][i + 1];

			if(b[j][i] == 1)dp[i][j] += dp[i + 1][i + 1];
		}
	}
	
	return dp[0][0];
}

/*
int main(){
	cout << count_tastiness(3, {5, 2, 1}) << endl;
	cout << count_tastiness(2, {2, 1, 2}) << endl;
	cout << count_tastiness(1, {2, 1, 2}) << endl;
	
	return 0;
}
*/

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