Submission #1230514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230514		Hamed_Ghaffari	Packing Biscuits (IOI20_biscuits)	C++20	100 / 100	19 ms	840 KiB

biscuits

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

using ll = long long;

#define SZ(x) int(x.size())

const int MXN = 60;

unordered_map<ll, ll> dp;
ll x;
ll s[MXN];

ll DP(ll n) {
    if(n<=1) return n==1;
    if(dp.find(n)!=dp.end()) return dp[n];
    int i = __lg(n-1);
    return dp[n] = DP(1ll<<i) + DP(min(n, s[i]/x+1)-(1ll<<i));
}

ll count_tastiness(ll x, vector<ll> a) {
    ::x = x;
    s[0] = a[0];
    for(int i=1; i<SZ(a); i++)
        s[i] = s[i-1] + (a[i]<<i);
    for(int i=SZ(a); i<60; i++) s[i] = s[i-1];
    dp.clear();
    return DP(1ll<<60);
}

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