Submission #311646

#	Time	Username	Problem	Language	Result	Execution time	Memory
311646		andrew	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	83 ms	1016 KiB

biscuits

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

#define fi first
#define se second
#define p_b push_back
#define m_p make_pair
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;

ll count_tastiness(ll x, vector <ll> a){
    ll ans = 0;
    vector <ll> b, c;
    ll _now = 0;
    for(int i = 0; i < sz(a) || _now; i++){
        c.p_b(_now);
        if(i < sz(a))_now += a[i];
        b.p_b(_now % 2);
        _now /= 2;
    }
    map <ll, ll> dp[63];
    dp[62][0] = 1;
    while(sz(b) < 63)b.p_b(0);
    while(sz(c) < 63)c.p_b(0);
    ll xt, t;
    for(int i = 61; i >= 0; i--){
        for(auto j : dp[i + 1]){
            xt = j.fi + b[i];
            if(xt >= x){
                dp[i][min(min(2 * x, (xt - x) * 2), 2 * c[i])] += j.se;
            }
            dp[i][min(min(2 * x, xt * 2), 2 * c[i])] += j.se;
        }
    }
    ans = 0;
    for(auto j : dp[0])ans += j.se;
    return ans;
}

Compilation message (stderr)

biscuits.cpp: In function 'll count_tastiness(ll, std::vector<long long int>)':
biscuits.cpp:30:12: warning: unused variable 't' [-Wunused-variable]
   30 |     ll xt, t;
      |            ^

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