Submission #1034601

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034601		12345678	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	18 ms	1372 KiB

biscuits

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

using namespace std;

#define ll long long

ll dp[62], p[62], qs[62], d;

ll solve(ll x)
{
    //cout<<"debug "<<x<<'\n';
    if (x==1) return 1;
    if (x<1) return 0;
    ll l=0, r=61;
    while (l<r)
    {
        ll md=(l+r+1)/2;
        if (p[md]<x) l=md;
        else r=md-1;
    }
    //cout<<"l "<<l<<' '<<x<<' '<<qs[l]/d<<' '<<min(x, qs[l]/d)-p[l]<<'\n';
    return dp[l]+solve(min(x, 1+qs[l]/d)-p[l]);
}

long long count_tastiness(long long x, std::vector<long long> a) {
    d=x;
    ll k=a.size(), cnt[62];
    vector<ll> res, tmp;
    p[0]=1;
    for (int i=1; i<62; i++) p[i]=p[i-1]*2, qs[i]=cnt[i]=0;
    for (int i=0; i<k; i++) cnt[i]=a[i];
    for (int i=0; i<62; i++) qs[i]=((i==0)?0:qs[i-1])+cnt[i]*p[i];
    dp[0]=1;
    for (int i=1; i<62; i++) dp[i]=solve(p[i]); //cout<<"dp "<<i<<' '<<dp[i]<<'\n';
    return dp[61];
}

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