Submission #333322

#	Time	Username	Problem	Language	Result	Execution time	Memory
333322		nickmet2004	Packing Biscuits (IOI20_biscuits)	C++14	100 / 100	92 ms	1004 KiB

biscuits

#include<bits/stdc++.h>
#include "biscuits.h"
#define ll long long
using namespace std;
ll Xk;
ll dp[61] , Pr[61];

ll Q(ll w){
    if(w < 0) return 0ll;
    if(w == 0) return 1ll;
    int j;
    for(j = 60; ~j; --j) if((1ll<<j) <= w) break;
    /// return dp[j] + x;
    return dp[j] + Q(min(w , Pr[j] / Xk) - (1ll<<j));
}
ll count_tastiness(ll X , vector<ll> a){
   Xk = X;
   a.resize(60);
   for(int i = 0; i < 60; ++i){
       Pr[i] = (1ll<<i) * a[i];
       if(i) Pr[i] += Pr[i - 1];
   }
   dp[0]= 1ll;
   for(int k = 1; k< 61; ++k) dp[k] = Q((1ll << k) - 1);
   return dp[60];
}

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