Submission #355593

#	Time	Username	Problem	Language	Result	Execution time	Memory
355593		doowey	Packing Biscuits (IOI20_biscuits)	C++14	100 / 100	102 ms	1388 KiB

biscuits

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

using namespace std;

typedef long long ll;

vector<ll> a;
map<ll,ll> dp;
ll x;

ll solve(ll n){ // how many <= n
    if(n < 0) return 0;
    if(n == 0) return 1;
    if(dp.count(n)) return dp[n];
    ll lg = 0;
    while((1ll<<(lg+1)) <= n) lg ++ ;
    ll sol = solve((1ll<<lg)-1); // last bit not included
    ll sum = 0;
    for(int i = 0 ; i <= lg; i ++ ){
        sum += (1ll << i) * 1ll * a[i];
    }
    sol += solve(min(sum/x,n)-(1ll<<lg));
    dp[n]=sol;
    return dp[n];
}

ll count_tastiness(ll _x, vector<ll> _a) {
    a = _a;
    x = _x;
    dp.clear();
    while(a.size() < 64) a.push_back(0);
	return solve((1ll<<61));
}

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