제출 #633870

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

biscuits

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

// editorial

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;
        }
    }
    auto F = [&](long long i) {
        if (i == 0) {
            return 0;
        } else {
            return 64 - __builtin_clzll(i);
        }
    };
    map<long long, long long> dp;
    dp[0] = 1;
    for (int i = 0; i < 61; i++) {
        map<long long, long long> new_dp;
        for (auto [k, v] : dp) {
            new_dp[F((a[i] + k) / 2)] += v;
            if (a[i] + k >= x) {
                new_dp[F((a[i] + k - x) / 2)] += v;
            }
        }
        swap(dp, new_dp);
    }
    return dp[0];
}

#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: 0 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 21
• Subtask 4: 0 / 35
• Subtask 5: 0 / 23