제출 #633813

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
633813		tabr	비스킷 담기 (IOI20_biscuits)	C++17	21 / 100	1105 ms	120764 KiB

biscuits

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

long long count_tastiness(long long x, vector<long long> a) {
    a.resize(62);
    for (int i = 0; i < 61; i++) {
        if (a[i] > x) {
            long long t = (a[i] - x) / 2;
            a[i] -= 2 * t;
            a[i + 1] += t;
        }
    }
    map<vector<long long>, long long> memo;
    function<long long(vector<long long>)> Solve = [&](vector<long long> b) {
        if (b.size() == 1) {
            return b[0] / x + 1;
        } else if (memo.count(b)) {
            return memo[b];
        }
        debug(b);
        long long res = 0;
        for (long long t : {0LL, x}) {
            if (b[0] < t) {
                continue;
            }
            auto c = b;
            c[1] += (c[0] - t) / 2;
            c.erase(c.begin());
            res += Solve(c);
        }
        return memo[b] = res;
    };
    return Solve(a);
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    debug(count_tastiness(3, {5, 2, 1}));  // 5
    debug(count_tastiness(2, {2, 1, 2}));  // 6
    return 0;
}
#endif

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