Submission #427491

#	Time	Username	Problem	Language	Result	Execution time	Memory
427491		AugustinasJucas	Packing Biscuits (IOI20_biscuits)	C++14	0 / 100	1086 ms	292 KiB

biscuits

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

long long count_tastiness(long long x, vector<long long> a) {
	if(x == 1){
		a.resize(150);
		for(int i = 0; i < 149; i++){
			if(a[i] <= 2) continue;
			int busiu = (a[i] % 2 == 0 ? 2 : 1);
			a[i + 1] += (a[i] - busiu) / 2ll;
			a[i] = busiu; 
		}
		while(a.size() > 1 && a.back() == 0) a.pop_back();
		
		long long dp[a.size() + 2][4];
		for(auto &x : dp) for(auto &y : x) y = 0;
		dp[a.size()][0] = 1;
		for(int i = a.size()-1; i > -1; i--){
			for(int j = 0; j <= 1; j++){
				// esu i, jau cia pliusas maziausiai j
				if(a[i] == 0){
					dp[i][j] = dp[i+1][0];
				}else if(a[i] == 1){
					if(j == 0){
						dp[i][0] = dp[i+1][0] * 2ll; // tikrai
					}else{
						dp[i][1] = dp[i+1][1] + dp[i+1][0]; // tikrai?
					}
				}else if(a[i] == 2){
					if(j == 0){
						dp[i][0] = dp[i+1][0] + dp[i+1][0] + dp[i+1][1];
					}else{
						dp[i][1] = dp[i+1][0] + dp[i+1][1] + dp[i+1][1];
					}
				}
			} 
		}
		
		
		return dp[0][0];
	}
	vector<long long> visi;
	int ans = 0;
	a.resize(30);
	for(int i = 0; i <= 100000; i++){
		auto kek = a;
		bool galima = 1;
		//cout << "bandau " << i << ":\n";
		for(int j = 0; j < 21; j++){
		//	cout << j << " bitu yra " << kek[j] <<endl;
			if(i & (1 << j)) {
				if(kek[j] < x) {
					galima = 0;
					break;
				}
				kek[j] -= x;
			}
			kek[j + 1] += kek[j] / 2;	
		}
		if(galima){
			//cout << i << " galima " << endl;
		}
		ans += galima;
	}
	return ans;
}

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