Submission #1065879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065879		vjudge1	Packing Biscuits (IOI20_biscuits)	C++17	0 / 100	1 ms	348 KiB

biscuits

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

using namespace std;

using ll = long long;
using vll = vector<ll>;
using i128 = __int128;

ll count_tastiness(ll x, vll a) {
    int n = int(a.size());
    vector<i128> S(n, 0);
    for(int i = 0; i < n; ++i) {
        S[i] = i128(1ll << i) * a[i];
        if(i) S[i] += S[i - 1];
    }
    vll C(n, 0);
    for(int i = 0; i < n; ++i) {
        S[i] /= x;
        if(S[i] >= i128(1ll << (i + 1)) - 1) C[i] = (1ll << (i + 1)) - 1;
        else C[i] = ll(S[i]);
    }
    vll F(n + 1, 0);
    F[0] = 1;

    function<ll(int, ll)> taie = [&](int k, ll lim) -> ll {
        if(lim < 0) return 0ll;
        if(lim >= (1ll << k) - 1) return F[k];
        //k > 0 de aici
        ll mij = (1ll << (k - 1)) - 1;
        if(lim <= mij) return taie(k - 1, lim);
        return taie(k - 1, lim - mij - 1) + F[k - 1];
    };
    for(int i = 1; i <= n; ++i) {
        //cout << C[i - 1] << " ";
        F[i] = F[i - 1] + taie(i - 1, C[i - 1] - (1ll << (i - 1)));
    }
//    cout << "\n";
//    for(auto it : F)
//        cout << it << " ";
//    cout << "\n";
	return F.back();
}

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