oj.uz

Submission #932094

# Submission time Handle Problem Language Result Execution time Memory
932094 2024-02-23T01:18:48 Z beaboss Packing Biscuits (IOI20_biscuits) C++14
0 / 100
 16 ms 504 KB 
// 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 += (1ll << j) * a[j]; // biscuits we have
			ll groups = (tot / x) >> j ; // stuff we can make here, wrt j
			mx = 2ll * mx + 1ll; // add extra 1 bit
			// cout << mx << endl;
			groups = min(groups, mx);

			groups++; // being empty

			// 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];

}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -