Submission #1269589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269589		biank	Packing Biscuits (IOI20_biscuits)	C++20	100 / 100	48 ms	840 KiB

biscuits

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

using namespace std;

#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)

#define all(x) begin(x), end(x)
#define sz(x) int(x.size())

#define pb push_back
#define eb emplace_back

using ll = long long;

const int K = 60;

ll s[K], X;
map<ll, ll> memo;

ll dp(ll n) {
    if (n <= 1) return n == 1;
    if (memo.count(n)) return memo[n];
    int i = 63 - __builtin_clzll(n - 1);
    return memo[n] = dp(1LL << i) + dp(min(n, s[i] / X + 1) - (1LL << i));
}

ll count_tastiness(ll x, vector<ll> a) {
    forn(i, sz(a)) if (a[i] - x >= 2) {
        ll extra = (a[i] - x) / 2;
        assert(extra >= 1);
        a[i] -= 2 * extra;
        if (i + 1 == sz(a)) a.pb(0LL);
        a[i + 1] += extra;
    }
    a.resize(K, 0);
    forn(i, K) s[i] = a[i] << i;
    forn(i, K - 1) s[i + 1] += s[i];
    X = x, memo.clear();
    return dp(1LL << K);
}

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