# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
356846 | 2021-01-23T21:05:14 Z | Kerim | Packing Biscuits (IOI20_biscuits) | C++17 | 859 ms | 1132 KB |
#include "biscuits.h" #include "bits/stdc++.h" #define ff first #define ss second using namespace std; typedef long long ll; ll X,tmp;vector<ll>a; map<ll,ll>dp[61]; ll rec(int pos,ll cur){ if(pos==61)return 1; __typeof((dp[pos]).begin())it=dp[pos].lower_bound(cur),itt; if(it!=dp[pos].end()){ if(it->ff==cur)return it->ss;itt=it; if(itt!=dp[pos].begin()){itt--;if(itt->ss==it->ss)return it->ss;} } ll &ret=dp[pos][cur]; ret=rec(pos+1,(cur+a[pos])/2); if(a[pos]+cur>=X)ret+=rec(pos+1,(a[pos]+cur-X)/2); it=dp[pos].upper_bound(cur); if(it!=dp[pos].end() and it->ss==ret){ itt=it;itt++; if(itt!=dp[pos].end() and itt->ss==ret) dp[pos].erase(it); }it--; if(it!=dp[pos].begin()){it--; if(it->ss==ret){itt=it; if(itt!=dp[pos].begin()){itt--; if(itt->ss==ret)dp[pos].erase(it); } } } return ret; } long long count_tastiness(long long x, vector<long long> A) {X=x;a=A; for(int i=0;i<61;i++)dp[i].clear(); while(int(a.size())<61)a.push_back(0); for(int i=0;i<60;i++)if(a[i]>x)tmp=(a[i]-x)/2,a[i+1]+=tmp,a[i]-=tmp<<1; return rec(0,0); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 1 ms | 364 KB | Output is correct |
7 | Correct | 1 ms | 364 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 364 KB | Output is correct |
11 | Correct | 1 ms | 364 KB | Output is correct |
12 | Correct | 1 ms | 364 KB | Output is correct |
13 | Correct | 1 ms | 364 KB | Output is correct |
14 | Correct | 1 ms | 364 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 1 ms | 364 KB | Output is correct |
7 | Correct | 1 ms | 364 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 2 ms | 364 KB | Output is correct |
3 | Correct | 2 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 1 ms | 364 KB | Output is correct |
7 | Correct | 1 ms | 364 KB | Output is correct |
8 | Correct | 2 ms | 384 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 364 KB | Output is correct |
11 | Correct | 4 ms | 364 KB | Output is correct |
12 | Correct | 7 ms | 364 KB | Output is correct |
13 | Correct | 8 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 37 ms | 364 KB | Output is correct |
2 | Correct | 150 ms | 1004 KB | Output is correct |
3 | Correct | 138 ms | 936 KB | Output is correct |
4 | Correct | 131 ms | 1004 KB | Output is correct |
5 | Correct | 119 ms | 876 KB | Output is correct |
6 | Correct | 205 ms | 876 KB | Output is correct |
7 | Correct | 211 ms | 936 KB | Output is correct |
8 | Correct | 190 ms | 1060 KB | Output is correct |
9 | Correct | 175 ms | 876 KB | Output is correct |
10 | Correct | 95 ms | 876 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 1 ms | 364 KB | Output is correct |
7 | Correct | 1 ms | 364 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 364 KB | Output is correct |
11 | Correct | 1 ms | 364 KB | Output is correct |
12 | Correct | 1 ms | 364 KB | Output is correct |
13 | Correct | 1 ms | 364 KB | Output is correct |
14 | Correct | 1 ms | 364 KB | Output is correct |
15 | Correct | 1 ms | 364 KB | Output is correct |
16 | Correct | 1 ms | 364 KB | Output is correct |
17 | Correct | 1 ms | 364 KB | Output is correct |
18 | Correct | 1 ms | 364 KB | Output is correct |
19 | Correct | 1 ms | 364 KB | Output is correct |
20 | Correct | 1 ms | 364 KB | Output is correct |
21 | Correct | 1 ms | 364 KB | Output is correct |
22 | Correct | 1 ms | 364 KB | Output is correct |
23 | Correct | 1 ms | 364 KB | Output is correct |
24 | Correct | 1 ms | 364 KB | Output is correct |
25 | Correct | 2 ms | 364 KB | Output is correct |
26 | Correct | 2 ms | 364 KB | Output is correct |
27 | Correct | 1 ms | 364 KB | Output is correct |
28 | Correct | 1 ms | 364 KB | Output is correct |
29 | Correct | 1 ms | 364 KB | Output is correct |
30 | Correct | 1 ms | 364 KB | Output is correct |
31 | Correct | 2 ms | 384 KB | Output is correct |
32 | Correct | 1 ms | 364 KB | Output is correct |
33 | Correct | 1 ms | 364 KB | Output is correct |
34 | Correct | 4 ms | 364 KB | Output is correct |
35 | Correct | 7 ms | 364 KB | Output is correct |
36 | Correct | 8 ms | 384 KB | Output is correct |
37 | Correct | 37 ms | 364 KB | Output is correct |
38 | Correct | 150 ms | 1004 KB | Output is correct |
39 | Correct | 138 ms | 936 KB | Output is correct |
40 | Correct | 131 ms | 1004 KB | Output is correct |
41 | Correct | 119 ms | 876 KB | Output is correct |
42 | Correct | 205 ms | 876 KB | Output is correct |
43 | Correct | 211 ms | 936 KB | Output is correct |
44 | Correct | 190 ms | 1060 KB | Output is correct |
45 | Correct | 175 ms | 876 KB | Output is correct |
46 | Correct | 95 ms | 876 KB | Output is correct |
47 | Correct | 92 ms | 608 KB | Output is correct |
48 | Correct | 28 ms | 876 KB | Output is correct |
49 | Correct | 16 ms | 364 KB | Output is correct |
50 | Correct | 26 ms | 748 KB | Output is correct |
51 | Correct | 14 ms | 876 KB | Output is correct |
52 | Correct | 6 ms | 364 KB | Output is correct |
53 | Correct | 17 ms | 748 KB | Output is correct |
54 | Correct | 784 ms | 876 KB | Output is correct |
55 | Correct | 859 ms | 1132 KB | Output is correct |
56 | Correct | 777 ms | 1004 KB | Output is correct |
57 | Correct | 600 ms | 952 KB | Output is correct |