Submission #1069829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069829		jerzyk	Packing Biscuits (IOI20_biscuits)	C++17	0 / 100	71 ms	1772 KiB

biscuits

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

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1000 * 1000 + 7;
ll il[N];
vector<pair<ll, ll>> zbi; ll answer = 0LL;

void Upd(ll b, ll lim)
{
    vector<pair<ll, ll>> nxt;
    for(int i = 0; i < (int)zbi.size() && (zbi[i].st <= lim); ++i)
    {
        pair<ll, ll> nw = make_pair(b + zbi[i].st, b + min(lim, zbi[i].nd));
        answer += nw.nd - nw.st + 1LL;
        nxt.pb(nw);
    }
    if((int)nxt.size() > 0)
    {
        int i = (int)zbi.size() - 1;
        if(zbi[i].nd + 1LL == nxt[0].st)
        {
            nxt[0].st = zbi[i].st;
            zbi.pop_back();
        }
    }
    for(int i = 0; i < (int)nxt.size(); ++i)
        zbi.pb(nxt[i]);
}

long long count_tastiness(long long x, std::vector<long long> _a)
{
    zbi.clear(); answer = 0LL;
    int n = _a.size() - 1;
    for(int i = 0; i <= n; ++i)
        il[i] = _a[i];
    if(il[0] >= x)
    {
        answer += 2LL;
        zbi.pb(make_pair(0LL, 1LL));
    }
    else
    {
        answer += 1LL;
        zbi.pb(make_pair(0LL, 0LL));
    }
    //cerr << "DP: \n";
    for(int i = 1; i <= 20; ++i)
    {
        if(x * (1LL<<(ll)i) > I) break;
        il[i] *= (1LL<<(ll)i);
        ll ned = max(0LL, (x * (1LL<<(ll)i) - il[i]));
        ll lim = (il[i - 1] - ned) / x;
        lim = min(lim, (1LL<<(ll)(i)) - 1LL);
        //cerr << i << " " << "bis: " << ned << " " << lim << "\n";
        if(lim >= 0LL)
            Upd((1LL<<(ll)i), lim);
        il[i] += il[i - 1];
    }
    for(int i = 0; i <= 100; ++i)
        il[i] = 0LL;
    return answer;
}

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