Submission #540722

#	Time	Username	Problem	Language	Result	Execution time	Memory
540722		alextodoran	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	40 ms	832 KiB

biscuits

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>
#include "biscuits.h"

using namespace std;

typedef long long ll;

ll x;
vector <ll> s;

unordered_map <ll, ll> save;

ll solve (ll n) {
    if (n <= 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        if (save.find(n) == save.end()) {
            int l = 0;
            while (((ll) 1 << (l + 1)) < n) {
                l++;
            }
            save[n] = solve(((ll) 1 << l)) + solve(min(n, 1 + s[l] / x) - ((ll) 1 << l));
        }
        return save[n];
    }
}

ll count_tastiness (ll _x, vector <ll> a) {
    while ((int) a.size() < 60) {
        a.push_back(0);
    }
    s.clear();
    save.clear();
    x = _x;
    for (int i = 0; i < (int) a.size(); i++) {
        s.push_back((s.empty() == false ? s.back() : 0) + (a[i] << i));
    }
    return solve((ll) 1 << 60);
}

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