Submission #622493

#	Time	Username	Problem	Language	Result	Execution time	Memory
622493		wiwiho	Packing Biscuits (IOI20_biscuits)	C++14	100 / 100	17 ms	1336 KiB

biscuits

#include "biscuits.h"

#include <bits/stdc++.h>

#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define eb emplace_back
#define ef emplace_front
#define pob pop_back()
#define pof pop_front()
#define mp make_pair
#define F first
#define S second
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

typedef long long ll;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

const int K = 61;
long long count_tastiness(ll x, vector<ll> a){
    
    a.resize(K);
    vector<ll> s(K);
    for(int i = 0; i < K; i++){
        s[i] = a[i] * (1LL << i);
        if(i) s[i] += s[i - 1];
    }

    vector<ll> dp(K); // g(2^i) = dp[i];
    dp[0] = 1;

    function<ll(ll)> g = [&](ll n) -> ll{
        if(n <= 0) return 0;
        if((1LL << __lg(n)) == n) return dp[__lg(n)];
        int i = __lg(n);
        return g(1LL << i) + g(min(n, s[i] / x + 1) - (1LL << i));
    };

    for(int i = 1; i < K; i++){
        ll n = 1LL << i;
        dp[i] = dp[i - 1] + g(min(n, s[i - 1] / x + 1) - (1LL << (i - 1)));
    }

    return dp[K - 1];
}

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