Submission #623913

#	Time	Username	Problem	Language	Result	Execution time	Memory
623913		ollel	Packing Biscuits (IOI20_biscuits)	C++17	0 / 100	894 ms	2097152 KiB

biscuits

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

#include "biscuits.h"

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long ll;
typedef vector<bool> vb;
typedef pair<int,int> pii;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define pb push_back


ll count_tastiness(ll x, vector<ll> a) {
	int k = a.size() * 40;
	rep(i,0,k) a.pb(0);

	rep(i,0,k-1) {
		if (a[i] <= x) continue;

		a[i + 1] += (a[i] - x) / 2;
		a[i] = x;
	}
	assert(a[k-1] == 0);

	vector<vector<ll>> dp(k, vector<ll>(2*x, 0));
	dp[0][a[0]] = 1;
	if (a[0] == x) dp[0][0] = 1;

	rep(i,0,k-1) rep(j,0,2*x) {
		dp[i+1][a[i+1] + j/2] += dp[i][j];
		if (a[i+1] + j/2 >= x) dp[i+1][a[i+1] + j/2 - x] += dp[i][j];
	}

	ll ans = 0;
	rep(j,0,2*x) ans += dp[k-1][j];

	return ans;
}

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