Submission #417929

#	Time	Username	Problem	Language	Result	Execution time	Memory
417929		TheScrasse	Packing Biscuits (IOI20_biscuits)	C++14	100 / 100	25 ms	1340 KiB

biscuits

// IOI20_biscuits

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

#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<

#define INF (ll)1e18
#define mod 1000000007
#define maxn 66

ll i, i1, j, k, k1, t, n, m, res, flag[10], a[maxn], b[maxn];
ll x, dp[maxn], l;

void solve(ll u, ll p) {
    // cout << "solve " << u _ p _ a[p] << nl;
    ll i;

    if (a[p] >= x) {
        dp[u] += dp[p - 1]; return;
    }

    for (i = p - 1; i >= 1; i--) {
        if (a[p] < -INF) return;
        a[p] = 2 * a[p] - x;
        if (x - a[p] <= a[i]) {
            a[i] -= x - a[p]; a[p] = x;
        } else {
            a[p] += a[i]; a[i] = 0;
        }

        // cout << "i, a[p] = " << i _ a[p] << nl;
        if (a[p] >= x) {
            dp[u] += dp[i - 1];
            solve(u, i); return;
        }
    }
}

void reset() {
    ll i;
    for (i = 0; i < maxn; i++) a[i] = b[i];
}

long long count_tastiness(long long X, vector<long long> A) {
    for (i = 0; i < maxn; i++) {
        a[i] = 0; b[i] = 0;
    }

    x = X; n = A.size();
    for (i = 1; i <= n; i++) {
        a[i] = A[i - 1];
    }

    for (i = 1; i < maxn - 1; i++) {
        if (a[i] >= x) {
            k = (a[i] - x) / 2;
            a[i + 1] += k; a[i] -= (2 * k);
        }
    }

    for (i = 0; i < maxn; i++) b[i] = a[i];

    dp[0] = 1;
    for (i = 1; i < maxn; i++) {
        dp[i] = dp[i - 1];
        reset(); solve(i, i);
    }

    /* for (i = 0; i < maxn; i++) cout << dp[i] << ' ';
    cout << nl; */

    res = dp[maxn - 1];

    return res;
}

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