Submission #602955

#	Time	Username	Problem	Language	Result	Execution time	Memory
602955		MohamedFaresNebili	Packing Biscuits (IOI20_biscuits)	C++14	100 / 100	92 ms	1344 KiB

biscuits

#include <bits/stdc++.h>
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")

            using namespace std;

            using ll = long long;
            using ii = pair<ll, ll>;
            using vi = vector<int>;

            #define ff first
            #define ss second
            #define pb push_back
            #define all(x) (x).begin(), (x).end()
            #define lb lower_bound

            const int oo = 1000 * 1000 * 1000 + 7;

            ll N; vector<ll> V;
            map<ll, ll> DP;
            ll solve(ll i) {
                if(i <= 0) return 0;
                if(i == 1) return 1;
                if(DP.count(i)) return DP[i];
                ll K = 0;
                for(ll l = 0; l <= 60; l++) 
                    if((1LL << l) < i) K = l;
                ll best = solve((1LL << K));
                ll U = min(i, 1 + V[K] / N) - (1ll << K);
                best += solve(U);
                return DP[i] = best;
            }

            ll count_tastiness(ll X, vector<ll> A) {
                ll K = A.size(); N = X; V.clear(); DP.clear();
                for(ll l = 0; l <= 60; l++) {
                    ll U = (l < K ? A[l] : 0), P = (1LL << l);
                    V.push_back(U * P + (l > 0 ? V[l - 1] : 0));
                }
                return solve(V[K - 1] / X + 1);
            }

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