Submission #623917

#	Time	Username	Problem	Language	Result	Execution time	Memory
623917		ollel	Packing Biscuits (IOI20_biscuits)	C++17	12 / 100	1109 ms	276196 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() + 100;
	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 + ((a[i] - x) & 1);
	}

	vector<map<int,ll>> dp(k);
	dp[0][a[0]] = 1;
	if (a[0] >= x) dp[0][a[0] - x] = 1;

	rep(i,0,k-1) for (auto [j, val] : dp[i]) {
		if (dp[i+1].find(a[i+1] + j/2) == dp[i+1].end()) dp[i+1][a[i+1] + j/2] = 0;
		dp[i+1][a[i+1] + j/2] += val;
		if (a[i+1] + j/2 >= x) {
			if (dp[i+1].find(a[i+1] + j/2 - x) == dp[i+1].end()) dp[i+1][a[i+1] + j/2 - x] = 0;
			dp[i+1][a[i+1] + j/2 - x] += dp[i][j];
		}
	}

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

	return ans;
}

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