Submission #633876

#	Time	Username	Problem	Language	Result	Execution time	Memory
633876		tabr	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	72 ms	1336 KiB

biscuits

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

// editorial

long long count_tastiness(long long x, vector<long long> a) {
    a.resize(62);
    vector<long long> s(62);
    for (int i = 0; i < 62; i++) {
        s[i] = (i > 0 ? s[i - 1] : 0) + (a[i] << i);
    }
    map<long long, long long> memo;
    memo[1] = 1;
    function<long long(long long)> Solve = [&](long long n) {
        if (n <= 0) {
            return 0LL;
        }
        if (!memo.count(n)) {
            int i = 63 - __builtin_clzll(n - 1);
            memo[n] = Solve(1LL << i) + Solve(min(n, 1 + s[i] / x) - (1LL << i));
        }
        return memo[n];
    };
    return Solve(1LL << 61);
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    debug(count_tastiness(3, {5, 2, 1}));  // 5
    debug(count_tastiness(2, {2, 1, 2}));  // 6
    return 0;
}
#endif

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