Submission #303458

#	Time	Username	Problem	Language	Result	Execution time	Memory
303458		dacin21	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	123 ms	1016 KiB

biscuits

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

using ll = long long;

ll solve_2(ll x, vector<ll> a){
    const int k = 61;
    a.resize(61, 0);
    for(int i=0; i+1<k; ++i){
        const ll m = max<ll>(0, (a[i]-x)/2);
        a[i+1] += m;
        a[i] -= 2*m;
    }
    for(auto &e:a){
        assert(0 <= e && e <= x+1);
    }
    // top: dp[needed] -> cnt
    // time: min(x, 2^n-i)
    vector<map<ll, ll> > dp(k+1);
    dp[k][0] = 1;
    int max_s = 0;
    for(int i=k; i>0; --i){
        dp[i].erase(dp[i].upper_bound(x), dp[i].end());
        max_s = max<int>(max_s, dp[i].size());
        for(auto &e:dp[i]){
            const ll f = 2*e.first - a[i-1];
            // no carry
            dp[i-1][max<ll>(0, f)] += e.second;
            // one carry
            dp[i-1][max<ll>(0, f+x)] += e.second;
        }
        //debug << named(dp[i-1]) << "\n";
    }
    //debug << named(max_s) << "\n";
    return dp.front()[0];
}
long long count_tastiness(long long x, std::vector<long long> a) {
	return solve_2(x, a);
}

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