Submission #757947

#	Time	Username	Problem	Language	Result	Execution time	Memory
757947		PurpleCrayon	Packing Biscuits (IOI20_biscuits)	C++17	42 / 100	1078 ms	1236 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);
    for (int i = 0; i < n; i++) {
        cat cur = cat(1) << i;
        for (int j = i-1; j >= 0; j--) {
            cur ^= cat(1) << j;

            ll carry = 0;
            bool bad = 0;
            for (int k = 0; k <= i && !bad; k++) {
                carry /= 2;
                carry += a[k];
                if ((cur >> k) & 1) carry -= x;
                if (carry < 0) bad = 1;
            }

            if (bad) {
                cur ^= cat(1) << j;
            }
        }
        
        bool bad = 0;
        ll carry = 0;
        for (int k = 0; k <= i && !bad; k++) {
            carry /= 2;
            carry += a[k];
            if ((cur >> k) & 1) carry -= x;
            if (carry < 0) bad = 1;
        }

        if (bad) {
            assert(cur == cat(1) << i);
            bound[i] = -1;
        } else {
            bound[i] = cur ^ (cat(1) << i);
        }
    }

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

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