Submission #1041365

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041365		vjudge1	Packing Biscuits (IOI20_biscuits)	C++17	42 / 100	1064 ms	19792 KiB

biscuits

#include "biscuits.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,ll> dp,dp2;
int check(ll k,ll x,vector<ll>a){
    for(int i=0;i<60;i++){
        if(k&1ll<<i)
            a[i]-=x;
        if(a[i]<0)
            return 0;
        a[i+1]+=a[i]/2;
    }
    return 1;
}
ll count_tastiness(ll x, std::vector<ll> a) {
    while(a.size()<=60)
        a.push_back(0);
    if(x<=10000) {
        dp.clear();
        dp2.clear();
        dp[0]=1;
        ll ans=0;
        for(auto k:a){
            dp2.clear();
            for(auto[i,j]:dp){
                ll l=i+k;
                if(l>=x) dp2[(l-x)/2]+=j;
                dp2[l/2]+=j;
            }
            swap(dp,dp2); 
        }
        for(auto i:dp)
            ans+=i.second;
        return ans;
    } else {
        int ans=0;
        queue<pair<ll,int>> q;
        q.push({0,0});
        while(q.size()){
            auto[v,b]=q.front();
            q.pop();
            if(!check(v,x,a))continue;
            ans++;
            for(int i=b;i<60;i++)
                q.push({v|1ll<<i,i+1});
        }
        return ans;
    }
}

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