제출 #932092

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
932092		beaboss	비스킷 담기 (IOI20_biscuits)	C++14	0 / 100	10 ms	348 KiB

biscuits

// Source: https://oj.uz/problem/view/IOI20_biscuits
// 

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<ll, ll> pii;
typedef vector<pii> vpii;

typedef vector<ll> vi;

#define FOR(i, a, b) for (ll i = (a); i<b; i++)

bool ckmin(ll& a, ll b){ return b < a ? a = b, true : false; }

bool ckmax(ll& a, ll b){ return b > a ? a = b, true : false; }



ll count_tastiness(ll x, vector<ll> a) {

	vi dp(61);
	dp[0]=1;

	FOR(i, 1, 61) {
		ll mx = 0;
		ll alr = 0;
		ll tot = 0;

		for (ll j = i-1; j >= 0; j--) {
			tot += (1 << j) * a[j]; // biscuits we have
			ll groups = (tot >> j) / x ; // stuff we can make here, wrt j
			mx = 2ll * mx + 1ll; // add extra 1 bit
			// cout << mx << endl;
			groups = min(groups, mx);

			groups++;

			// cout << i << ' ' << groups << ' ' << alr << endl;
			// assert(alr <= groups);

			dp[i] += dp[j] * max(groups - alr, 0ll);

			alr = max(groups, alr) * 2ll;
		}
		// break;
	}

	return dp[60];

}

// int main() {
// 	cout << count_tastiness(3, {5, 2, 1}) << endl;
// }

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