Submission #1154342

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154342		dpsaveslives	비스킷 담기 (IOI20_biscuits)	C++20	100 / 100	19 ms	1152 KiB

biscuits

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

ll f[64],cnt[64],sum[64];
ll F(ll id,ll y,int op=1)
{
    if(id==0) return min(min(sum[0],y),1ll)+1;
    if(op==1 && y>=sum[id]) return f[id];
    ll res=F(id-1,y);
    if(y>=(1ll<<id+1)-1) res+=f[id-1];
    else if(y>=(1ll<<id)) res+=F(id-1,y-(1ll<<id));
    return res;
}
ll Solve(ll x)
{
    for(int i = 0;i<60;++i) sum[i]=cnt[i]*(1ll<<i);
    for(int i = 1;i<60;++i) sum[i]+=sum[i-1];
    for(int i = 0;i<60;++i) sum[i]/=x;
    for(int i = 0;i<60;++i) f[i]=F(i,sum[i],0);
    return f[59];
}
ll count_tastiness(ll x,vector<ll> a)
{
    memset(f,0,sizeof(f)),memset(cnt,0,sizeof(cnt));
    for(int i=0;i<a.size();++i) cnt[i]=a[i];
    return Solve(x);
}

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