Submission #1246200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246200		Boomyday	Packing Biscuits (IOI20_biscuits)	C++20	100 / 100	38 ms	840 KiB

biscuits

//
// Created by adavy on 7/23/2025.
//

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

void insert(map<ll,ll>& mp, ll i, ll x){
    if (mp.count(i)) {
        mp[i] += x;
    } else {
        mp[i] = x;
    }
}

long long count_tastiness(long long x, std::vector<long long> a) {
    int B = 60;
    while(a.size() <= B-1) a.push_back(0);
    vector<ll> divs(B);
    ll ctr = 0;
    for(int i=0;i<B;++i){
        ctr += (1LL<<i)*a[i];
        divs[i] = ctr/x;
    }
    ll ans = (1LL<<B);
    map<ll,ll> blocks; 
    blocks[(1LL<<B) - 1] = 1;
    ll t;
    for(ll i=B-1;i>=0;--i){
        map<ll,ll> blocks2;
        for(auto [k,v]:blocks){
            t = k;
            if (k > divs[i]){
                ans -= v*(k - divs[i]);
                t = divs[i];
            }
            insert(blocks2, t%(1LL<<i), v);
            if (t >= (1LL<<i)) insert(blocks2, (1LL<<i) - 1, v);
        }
        blocks = blocks2;
    }
    return ans;
}

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