Submission #389901

#	Time	Username	Problem	Language	Result	Execution time	Memory
389901		Osama_Alkhodairy	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	81 ms	1332 KiB

biscuits

#include <bits/stdc++.h>
#include "biscuits.h"
//~ #include "grader.cpp"
using namespace std;
#define ll long long

int k;
ll x;
vector <ll> a, s;
map <ll, ll> dp;

ll solve(ll p){
    if(p == 1) return 1;
    if(p <= 0) return 0;
    if(dp.count(p)) return dp[p];
    int b = __lg(p);
    if((p & (p - 1)) == 0) b--;
    return dp[p] = solve(1LL << b) + solve(min(p, 1 + s[b] / x) - (1LL << b));
}
long long count_tastiness(long long X, vector<long long> A){
    x = X;
    a = A;
    k = a.size();
    while(k < 60){
        a.push_back(0);
        k++;
    }
    s.clear();
    s.resize(k);
    for(int i = 0 ; i < k ; i++){
        if(i > 0) s[i] = s[i - 1];
        s[i] += (1LL << i) * a[i];
    }
    dp.clear();
    return solve(1LL << 60);
}

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