Submission #698972

#	Time	Username	Problem	Language	Result	Execution time	Memory
698972		sharaelong	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	129 ms	1324 KiB

biscuits

#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MAX_N = 60;

ll f[MAX_N];
map<pair<int, ll>, ll> dp;

ll solve(int i, ll j) {
    if (j < 0) return 0;
    if (i == 0) return (j == 0 ? 1 : (f[i] == 0 ? 1 : 2));
    if (dp.find({ i, j }) == dp.end()) dp[{i, j}] = -1;
    ll& ret = dp[{i,j}];
    if (ret != -1) return ret;

    ret = solve(i-1, min({ j, (1ll << i)-1, f[i] }))
        + solve(i-1, min({ j-(1ll << i), (1ll << i)-1, f[i]-(1ll << i) }));
    return ret;
}

ll count_tastiness(ll x, vector<ll> a) {
    for (int i=0; i<MAX_N; ++i) {
        ll sum = 0;
        for (int j=0; j<min(i+1, (int)a.size()); ++j) sum += a[j] * (1ll << j);
        f[i] = sum / x;
    }

    dp.clear();
    ll ret = solve(MAX_N-1, (1ll << MAX_N)-1);
    return ret;
}

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