Submission #757964

#	Time	Username	Problem	Language	Result	Execution time	Memory
757964		PurpleCrayon	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	113 ms	1364 KiB

biscuits

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

#define sz(v) int(v.size())
typedef long long ll;

const int SHIFT = 61;
using cat = __int128;

map<pair<int, cat>, ll> dp;
vector<cat> bound;

ll rec(int c, cat b) {
    if (c < 0) return 1;
    if (dp.count({c, b})) return dp[{c, b}];

    ll ans = 0;
    // set as a 0
    if ((b >> c) & 1) {
        ans += rec(c - 1, (cat(1) << c) - 1);
    } else {
        ans += rec(c - 1, b);
    }

    // set as a 1
    if (((b >> c) & 1) && bound[c] != -1) {
        ans += rec(c - 1, min(b ^ (cat(1) << c), bound[c]));
    }

    return dp[{c, b}] = ans;
}

long long count_tastiness(long long x, std::vector<long long> a) {
    int n = SHIFT + sz(a);
    while (sz(a) < n) a.push_back(0);

    dp.clear();
    bound.resize(n);
    vector<ll> pre(n);
    ll base = 0;
    for (int i = 0; i < n; i++) {
        base /= 2;
        pre[i] = base;
        base += a[i];
    }

    for (int i = 0; i < n; i++) {
        if (a[i] >= x) {
            bound[i] = (cat(1) << i) - 1;
            continue;
        }

        ll need = x - a[i];
        if (need > pre[i]) {
            bound[i] = -1;
            continue;
        }

        cat cur = 0;
        for (int j = i-1; j >= 0; j--) {
            need *= 2;
            if (pre[j] + a[j] - x >= need) {
                need -= a[j] - x;
                cur |= cat(1) << j;
            } else {
                need -= a[j];
            }
            need = max(need, 0LL);
        }

        bound[i] = cur;
    }

    return rec(n - 1, (cat(1) << n) - 1);
}

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