Submission #1057358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057358		_8_8_	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	10 ms	1472 KiB

biscuits

#include <bits/stdc++.h>
using namespace std;
// typedef long long ll;
const int N = 60 + 12;
using ll = __int128_t;
int k;
ll b[N],dp[N],c[N],pref[N];
int hsb(ll x) {
    for(int i = 60;i >= 0;i--) {
        if((x >> i) & 1) return i;
    }
    return -1;
}
long long count_tastiness(long long x, vector<long long> a){
    memset(dp,0,sizeof(dp));
    memset(pref,0,sizeof(pref));
    k = (int)a.size();
    ll all = 0;
    for(int i = 0;i < k;i++) {
        all += (1ll << i) * a[i];
    }
    for(int i = 0;i < k;i++) {
        c[i] = (1ll << i) * 1ll * x;
        a[i] = (1ll << i) * 1ll * a[i];       
        b[i] = a[i];
        if(i) 
            b[i] += b[i - 1];
        if((1ll << i)> all / x) {
            k = i;
            break;
        }
    }
    if(!k) {
        return 1;
    }
    int t = 59;
    for(int i = k;i <= t;i++) {
        if((1ll << i)> b[k - 1] / x) {
            t = i - 1;
            break;
        }
        c[i] = (1ll << i) * 1ll * x;
        b[i] = b[i - 1];
    }
    for(int i = 0;i <= t;i++) {
        if(i) pref[i] = pref[i - 1];
        if(b[i] < c[i]) {
            continue;
        }
        // cout << c[i] << '\n';
        dp[i] = 1;
        ll val = b[i] - c[i];
        for(int j = i - 1;j >= 0;j--) {
            if(dp[j] && val - c[j] >= 0) {
                val -= c[j];
                dp[i]++;
                val = min(val,b[j] - c[j]);
                if(j) {
                    dp[i] += pref[j - 1];
                }
            }
        }
        pref[i] += dp[i];
    }
    return pref[t] + 1;
}

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