# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
696333 | garam1732 | Packing Biscuits (IOI20_biscuits) | C++14 | 20 ms | 780 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 ii;
ll dp[100];
ll solve(ll x, vector<ll> a, bool full) {
if(a.empty()) return dp[0] = 1;
ll z = *a.rbegin(); int sz = a.size();
a.pop_back();
if(full && dp[sz]) return dp[sz];
ll q = z/x, res = 0;
res += (q+1)*solve(x, a, 1);
if(z % x) {
ii v = (ii)(x-z%x)*(1LL<<(sz-1));
for(int i = (int)a.size()-1; i >= 0; i--) {
if(v == 0) break;
else if(v >= (ii)a[i]*(1LL<<i)) {
v -= (ii)a[i]*(1LL<<i);
a.pop_back();
}
else {
a[i] -= v/(1LL<<i);
break;
}
}
if(v == 0) res += solve(x, a, 0);
}
if(full) dp[sz] = res;
return res;
}
long long count_tastiness(long long x, std::vector<long long> a) {
for(int i = 0; i <= a.size(); i++) {
dp[i] = 0;
for(int j = i+1; j < a.size(); j++) {
if(a[i]/x >= (1LL<<(j-i))-1) {
a[i] += a[j]*(1LL<<(j-i));
a[j] = 0;
}
}
}
return solve(x, a, 0);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |