Submission #303765

#	Time	Username	Problem	Language	Result	Execution time	Memory
303765		imeimi2000	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	75 ms	1024 KiB

biscuits

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

using namespace std;
typedef long long llong;

static const int N = 60;
static llong x;
static vector<llong> A, S;
static map<llong, llong> dp[60];

static llong get(int i, llong u) {
    if (i < 0) return !u;
    if (u > S[i]) return 0;
    if (dp[i].count(u)) return dp[i][u];
    llong ret = get(i - 1, 2 * max(0ll, u - A[i]));
    ret += get(i - 1, 2 * max(0ll, u + x - A[i]));
    return dp[i][u] = ret;
}

llong count_tastiness(llong _x, vector<llong> _A) {
    x = _x;
    A = _A;
    A.resize(N, 0);
    S.resize(N, 0);
    for (int i = 0; i < N; ++i) {
        dp[i].clear();
        if (A[i] >= x + 2) {
            A[i + 1] += (A[i] - x) / 2;
            A[i] -= (A[i] - x) / 2 * 2;
        }
        S[i] = A[i];
        if (i) S[i] += S[i - 1] / 2;
    }
    return get(N - 1, 0);
}

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