Submission #781520

#	Time	Username	Problem	Language	Result	Execution time	Memory
781520		_martynas	Packing Biscuits (IOI20_biscuits)	C++14	12 / 100	7 ms	1108 KiB

biscuits

#include "biscuits.h"
#include <set>
#include <iostream>
#include <assert.h>
#include <algorithm>
#include <numeric>

using namespace std;

using ll = long long;

#warning change mxk to 60
const int mxk = 60;

ll count_tastiness(ll x, vector<ll> a) {
    vector<ll> dp(mxk+1); // dp[i] - ways to use first i bits
    dp[0] = 1;
    a.resize(mxk, 0);
    vector<ll> pref(mxk);
    for(int i = 0; i < mxk; i++) {
        pref[i] = (i ? pref[i-1] : 0) + (1LL<<i)*a[i];
    }
//    for(int y : a) cerr << y << " ";
//    cerr << "\n";
    for(int i = 1; i <= mxk; i++) {
        // i-th bit is 0
        dp[i] = dp[i-1];
        // i-th bit is 1
        if(a[i-1] >= x) {
            dp[i] += dp[i-1];
        }
        else {
            ll mx = 1LL << (i-1);
            // x*mx can overflow
            if(1.0*x*mx > 1.5e18) continue;
            mx = pref[i-1]-x*mx;
            if(mx >= x*(1LL << (i-1))) {
                dp[i] += dp[i-1];
            }
            else if(mx >= 0) {
                dp[i]++;
                mx /= x;
                for(int b = 0; b < i-1; b++) {
                    if(mx & (1LL << b)) {
                        dp[i] += dp[b];
                    }
                }
            }
        }
    }
//    for(auto y : dp) cerr << y << " ";
//    cerr << "\n";
	return dp[mxk];
}

Compilation message (stderr)

biscuits.cpp:12:2: warning: #warning change mxk to 60 [-Wcpp]
   12 | #warning change mxk to 60
      |  ^~~~~~~

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