Submission #1269582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269582		biank	비스킷 담기 (IOI20_biscuits)	C++20	42 / 100	1096 ms	5256 KiB

biscuits

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

using namespace std;

#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)

#define all(x) begin(x), end(x)
#define sz(x) int(x.size())

#define pb push_back
#define eb emplace_back

using ll = long long;

ll count_tastiness(ll x, vector<ll> a) {
    if (x > 10000) {
        ll sum = 0;
        forn(i, sz(a)) sum += a[i] << i;
        ll ret = 1;
        for (ll y = 1; y * x <= sum; y++) {
            vector<ll> c = a;
            ll need = x;
            while (need) {
                ll curr = y;
                dforn(i, sz(a)) {
                    ll cnt = min(c[i], curr >> i);
                    c[i] -= cnt, curr -= cnt << i;
                }
                if (curr == 0) need--;
                else break;
            }
            if (need == 0) ret++;
        }
        return ret;
    }
    forn(i, sz(a)) if (a[i] - x >= 2) {
        ll extra = (a[i] - x) / 2;
        assert(extra >= 1);
        a[i] -= 2 * extra;
        if (i + 1 == sz(a)) a.pb(0LL);
        a[i + 1] += extra;
    }
    a.resize(60, 0);
    vector<vector<ll>> dp(sz(a) + 1, vector<ll>(x + 2, 0));
    dp[sz(a)] = vector<ll>(x + 2, 1);
    dforn(i, sz(a)) forn(j, x + 2) {
        dp[i][j] = dp[i + 1][(j + a[i]) / 2];
        if (j + a[i] >= x) dp[i][j] += dp[i + 1][(j + a[i] - x) / 2];
    }
    return dp[0][0];
}

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