제출 #1234209

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1234209		SpyrosAliv	비스킷 담기 (IOI20_biscuits)	C++20	12 / 100	3 ms	328 KiB

biscuits

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

ll count_tastiness(ll x, vector<ll> a) {
	while (a.size() < 60) a.push_back(0);
	int k = a.size();
	for (int i = 0; i < k-1; i++) {
		if (a[i] <= 2) continue;
		ll extra = a[i] - 1;
		a[i+1] += extra / 2LL;
		if (a[i] % 2) a[i] = 1;
		else a[i] = 2;
	}
	for (int i = 0; i < k; i++) assert(a[i] <= 2);
	vector<ll> po(k);
	po[0] = 1LL;
	for (int i = 1; i < k; i++) po[i] = po[i-1] * 2LL;
	vector<vector<ll>> dp(k, vector<ll>(2, 0LL));
	if (a[0]) {
		dp[0][0] = dp[0][1] = 1;
	}
	else {
		dp[0][0] = 1;
		dp[0][1] = 0;
	}
	for (int i = 1; i < k; i++) {
		if (a[i]) {
			dp[i][0] = dp[i-1][0] + dp[i-1][1];
			dp[i][1] = dp[i-1][0] + dp[i-1][1];
		}
		else {
			dp[i][0] = dp[i-1][0] + dp[i-1][1];
			for (int j = i-1; j >= 0; j--) {
				if (a[j] == 0) break;
				if (a[j] == 1) continue;
				dp[i][1] += dp[j][0];
			}
		}
	}
	return dp[k-1][0] + dp[k-1][1];
}

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