#include "biscuits.h"
#include <iostream>
#include <unordered_map>
#include <map>
#include <utility>
#include <functional>
#include <cassert>
#include <set>
#include <random>
using namespace std;
using ll = long long ;
ll x;
vector<ll> a;
map<ll, ll> dp[61];
mt19937 rnd(453);
ll calc(ll rem, ll i) {
if(i>=(int)a.size()) return 1LL<<(rem/x);
auto it=dp[i].lower_bound(rem);
if(it!=dp[i].end() && it->first==rem) return dp[i][rem];
if(it!=dp[i].end() && it!=dp[i].begin()) {
if(it->second==prev(it)->second) {
return it->second;
}
}
ll orig=rem;
if(i<(int)a.size() || rem>=x) {
if(i<(int)a.size()) {
rem+=a[i];
}
ll ans=0;
if(rem>=x) {
if(i&1) {
ans+=calc(rem/2, i+1);
ans+=calc((rem-x)/2, i+1);
}else {
ans+=calc((rem-x)/2, i+1);
ans+=calc(rem/2, i+1);
}
}else {
ans+=calc(rem/2, i+1);
}
return dp[i][orig]=ans;
}else {
return 1;
}
}
ll count_tastiness(ll x_, vector<ll> a_) {
a=a_;
x=x_;
a.resize(60);
for(int i=0;i<60;++i) {
if(a[i]>=x+2) {
ll diff=a[i]-(x+1);
a[i]-=(diff+1)/2*2;
a[i+1]+=(diff+1)/2;
}
}
while(a.back()==0) a.pop_back();
for(auto& i:dp) i.clear();
return calc(0, 0);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
2 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
2 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
3 ms |
332 KB |
Output is correct |
12 |
Correct |
6 ms |
460 KB |
Output is correct |
13 |
Correct |
7 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
332 KB |
Output is correct |
2 |
Correct |
200 ms |
844 KB |
Output is correct |
3 |
Correct |
193 ms |
932 KB |
Output is correct |
4 |
Correct |
176 ms |
912 KB |
Output is correct |
5 |
Correct |
164 ms |
900 KB |
Output is correct |
6 |
Correct |
221 ms |
924 KB |
Output is correct |
7 |
Correct |
222 ms |
924 KB |
Output is correct |
8 |
Correct |
215 ms |
912 KB |
Output is correct |
9 |
Correct |
222 ms |
920 KB |
Output is correct |
10 |
Correct |
142 ms |
904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
0 ms |
204 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
0 ms |
204 KB |
Output is correct |
22 |
Correct |
0 ms |
204 KB |
Output is correct |
23 |
Correct |
0 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
2 ms |
332 KB |
Output is correct |
27 |
Correct |
0 ms |
204 KB |
Output is correct |
28 |
Correct |
0 ms |
204 KB |
Output is correct |
29 |
Correct |
1 ms |
204 KB |
Output is correct |
30 |
Correct |
1 ms |
204 KB |
Output is correct |
31 |
Correct |
2 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
3 ms |
332 KB |
Output is correct |
35 |
Correct |
6 ms |
460 KB |
Output is correct |
36 |
Correct |
7 ms |
460 KB |
Output is correct |
37 |
Correct |
27 ms |
332 KB |
Output is correct |
38 |
Correct |
200 ms |
844 KB |
Output is correct |
39 |
Correct |
193 ms |
932 KB |
Output is correct |
40 |
Correct |
176 ms |
912 KB |
Output is correct |
41 |
Correct |
164 ms |
900 KB |
Output is correct |
42 |
Correct |
221 ms |
924 KB |
Output is correct |
43 |
Correct |
222 ms |
924 KB |
Output is correct |
44 |
Correct |
215 ms |
912 KB |
Output is correct |
45 |
Correct |
222 ms |
920 KB |
Output is correct |
46 |
Correct |
142 ms |
904 KB |
Output is correct |
47 |
Correct |
104 ms |
408 KB |
Output is correct |
48 |
Correct |
21 ms |
836 KB |
Output is correct |
49 |
Correct |
13 ms |
384 KB |
Output is correct |
50 |
Correct |
19 ms |
728 KB |
Output is correct |
51 |
Correct |
10 ms |
764 KB |
Output is correct |
52 |
Correct |
2 ms |
332 KB |
Output is correct |
53 |
Correct |
8 ms |
716 KB |
Output is correct |
54 |
Correct |
819 ms |
1348 KB |
Output is correct |
55 |
Correct |
945 ms |
1100 KB |
Output is correct |
56 |
Correct |
922 ms |
1608 KB |
Output is correct |
57 |
Correct |
732 ms |
1444 KB |
Output is correct |