Submission #1240451

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240451		Ghulam_Junaid	Packing Biscuits (IOI20_biscuits)	C++20	47 / 100	194 ms	54256 KiB

biscuits

#include <bits/stdc++.h>
#include "biscuits.h"
// #include "grader.cpp"
using namespace std;

typedef long long ll;

map<vector<ll>, ll> memo;
vector<ll> nvec;
ll x;

ll f(vector<ll> vec){
    if (memo.find(vec) != memo.end()) 
        return memo[vec];
    
    ll sz = vec.size();
    if (sz == 0) 
        return memo[vec] = 1;

    nvec = vec;
    if (vec.back() >= x){
        nvec.pop_back();
        return memo[vec] = 2 * f(nvec);
    }
    nvec.pop_back();

    ll tmp = f(nvec);
    if ((1ll << (sz - 1)) > (1e18 + x) / (x - vec.back()))
        return memo[vec] = tmp;

    nvec = vec;
    nvec.pop_back();

    ll cur = (x - vec.back()) * (1ll << (sz - 1));
    for (ll i = sz - 2; i >= 0; i --){
        if (cur >= (1ll << i) and nvec[i]){
            ll quo = min(nvec[i], cur / (1ll << i));
            nvec[i] -= quo;
            cur -= quo * (1ll << i);
        }
    }

    if (cur == 0) return memo[vec] = tmp + f(nvec);
    return memo[vec] = tmp;
}

ll count_tastiness(ll X, vector<ll> a){
    x = X;
    ll k = a.size();
    ll ans = 1;

    while (a.size() < 60)
        a.push_back(0);
    for (ll i = 0; i + 1 < a.size(); i ++){
        if (a[i] < 2 * x + 1) continue;
        ll del = (a[i] - x) / 2;
        a[i] -= 2 * del;
        a[i + 1] += del;
    }
	return f(a);
}

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