# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
546872 | LucaDantas | Packing Biscuits (IOI20_biscuits) | C++17 | 1078 ms | 612 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;
long long brute(long long x, std::vector<long long> a) {
long long ans = 0;
while(a.size() < 20) a.push_back(0);
for(int mask = 0; mask <= 100000; mask++) {
long long tem = 0;
bool ok = 1;
for(int b = 0; b < 20; b++) {
tem += a[b];
if(mask&(1<<b)) {
if(tem >= x) tem -= x;
else {ok = 0; break;}
}
tem >>= 1;
}
ans += ok;
}
return ans;
}
long long x_leq_10000(long long x, std::vector<long long> a) {
while(a.size() < 128) a.push_back(0);
int atv = 0;
for(int i = 0; i+1 < a.size(); i++) {
if(a[i]&1) a[i+1] += a[i]/2, a[i] = 1;
else a[i+1] += max(0ll, a[i]/2-1), a[i] = min(a[i], 2ll);
atv += a[i] > 0;
}
long long dp[20010]{}, new_dp[20010]{};
dp[0] = 1, dp[x] = 1;
for(int i = (int)(a.size()) - 1; i >= 0; i--) {
for(int qtd = 0; qtd <= x; qtd++)
new_dp[qtd] = dp[(a[i] + qtd)/2] + (a[i]+qtd >= x ? dp[(a[i] + qtd - x) / 2] : 0);
for(int qtd = 0; qtd <= x; qtd++)
dp[qtd] = new_dp[qtd];
}
return dp[0];
}
long long count_tastiness(long long x, std::vector<long long> a) {
if(x <= 10000) return x_leq_10000(x, a);
return brute(x, a);
}
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... |