Submission #828839

#	Time	Username	Problem	Language	Result	Execution time	Memory
828839		Abrar_Al_Samit	Packing Biscuits (IOI20_biscuits)	C++17	21 / 100	1082 ms	63208 KiB

biscuits

#include <bits/stdc++.h>
#include "biscuits.h"

using namespace std;

int k = 122;
vector<long long>a;

long long x;
map<long long, long long>dp[125];

long long solve(int i, long long j) {
	if(i>=k) return 1;

	if(dp[i].find(j)!=dp[i].end()) return dp[i][j];
	long long &ret = dp[i][j];

	long long cr = a[i] + j;

	ret = solve(i+1, cr/2);
	if(cr>=x) ret += solve(i+1, (cr-x)/2);
	return ret;
}
long long count_tastiness(long long X, vector<long long> A) {
	A.resize(122);
	a = A, x = X;

	for(int i=0; i<k-1; ++i) {
		if(a[i]<=x) continue;
		long long take = max(0LL, a[i] - x);
		a[i] -= take - (take & 1);
		a[i+1] += take / 2;
	}
	for(int i=0; i<125; ++i) dp[i].clear();
	return solve(0, 0);
}

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