Submission #1154340

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154340		dpsaveslives	Packing Biscuits (IOI20_biscuits)	C++20	35 / 100	6 ms	840 KiB

biscuits

#include <bits/stdc++.h>
#define ll long long
#include "biscuits.h"
using namespace std;
ll dp[65],sum[65],arr[65];
ll calc(ll pos, ll y, int p){
    if(pos == 0) return min(min(sum[0],y),1ll)+1;
    if(p == 1 && y >= sum[pos]) return dp[pos];
    ll res = calc(pos-1,y,1);
    if(y >= (1ll<<(pos+1))-1){
        res += dp[pos-1];
    }
    else if(y >= (1ll<<pos)){
        res += calc(pos-1,y-(1ll<<pos),1);
    }
    return res;
}
ll count_tastiness(ll x, vector<ll> a){
    memset(dp,0,sizeof(dp));
    for(int i = 0;i<a.size();++i) arr[i] = a[i];
    for(int i = 0;i<60;++i){
        sum[i] = arr[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){
        dp[i] = calc(i,sum[i],0);
    }
    return dp[59];
}

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