#include <bits/stdc++.h>
#include "biscuits.h"
using namespace std;
map <long long , long long> mp[61];
long long s[61];
long long x2;
long long rec (int bit , long long nr){
long long sum = 0;
if (bit < 0)
return 1;
nr = min(nr , s[bit] / x2);
nr = min(nr , (1LL << (bit + 1)));
if (mp[bit].find(nr) != mp[bit].end()){ /// exista deja
return mp[bit][nr];
}
if ((1LL << bit) <= nr){ /// nr tine de s[i], de asta, asta ins ca poate fi bitul 1
sum += rec(bit - 1 , nr - (1LL << bit));
}
/// altfel pui bitul 0 aici
sum += rec (bit - 1 , nr);
mp[bit][nr] = sum;
return sum;
}
long long count_tastiness(long long x, vector<long long> a) {
int i;
x2 = x;
for (i = 0 ; i <= 60 ; i++){
mp[i].clear();
s[i] = 0;
}
s[60] = 0;
for (i = 0 ; i <= 60 ; i++){
if (i < a.size())
s[i] += a[i] * (1LL << i);
if (i)
s[i] += s[i - 1];
}
/// s[i] / x e un fel de maxim posibil sa ai pana la i
return rec(60 , min( s[60] / x , (1LL << 60) ) );
}
Compilation message
biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:49:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | if (i < a.size())
| ~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
0 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
256 KB |
Output is correct |
6 |
Correct |
1 ms |
256 KB |
Output is correct |
7 |
Correct |
0 ms |
256 KB |
Output is correct |
8 |
Correct |
1 ms |
256 KB |
Output is correct |
9 |
Correct |
0 ms |
256 KB |
Output is correct |
10 |
Correct |
1 ms |
256 KB |
Output is correct |
11 |
Correct |
0 ms |
256 KB |
Output is correct |
12 |
Correct |
1 ms |
256 KB |
Output is correct |
13 |
Correct |
1 ms |
256 KB |
Output is correct |
14 |
Correct |
1 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
256 KB |
Output is correct |
6 |
Correct |
1 ms |
288 KB |
Output is correct |
7 |
Correct |
1 ms |
256 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
256 KB |
Output is correct |
6 |
Correct |
1 ms |
256 KB |
Output is correct |
7 |
Correct |
1 ms |
256 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
256 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
384 KB |
Output is correct |
2 |
Correct |
30 ms |
896 KB |
Output is correct |
3 |
Correct |
29 ms |
896 KB |
Output is correct |
4 |
Correct |
28 ms |
896 KB |
Output is correct |
5 |
Correct |
27 ms |
896 KB |
Output is correct |
6 |
Correct |
36 ms |
1016 KB |
Output is correct |
7 |
Correct |
34 ms |
896 KB |
Output is correct |
8 |
Correct |
32 ms |
896 KB |
Output is correct |
9 |
Correct |
31 ms |
896 KB |
Output is correct |
10 |
Correct |
22 ms |
896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
0 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
256 KB |
Output is correct |
6 |
Correct |
1 ms |
256 KB |
Output is correct |
7 |
Correct |
0 ms |
256 KB |
Output is correct |
8 |
Correct |
1 ms |
256 KB |
Output is correct |
9 |
Correct |
0 ms |
256 KB |
Output is correct |
10 |
Correct |
1 ms |
256 KB |
Output is correct |
11 |
Correct |
0 ms |
256 KB |
Output is correct |
12 |
Correct |
1 ms |
256 KB |
Output is correct |
13 |
Correct |
1 ms |
256 KB |
Output is correct |
14 |
Correct |
1 ms |
256 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
256 KB |
Output is correct |
17 |
Correct |
1 ms |
256 KB |
Output is correct |
18 |
Correct |
1 ms |
256 KB |
Output is correct |
19 |
Correct |
1 ms |
256 KB |
Output is correct |
20 |
Correct |
1 ms |
288 KB |
Output is correct |
21 |
Correct |
1 ms |
256 KB |
Output is correct |
22 |
Correct |
1 ms |
384 KB |
Output is correct |
23 |
Correct |
1 ms |
384 KB |
Output is correct |
24 |
Correct |
1 ms |
256 KB |
Output is correct |
25 |
Correct |
0 ms |
256 KB |
Output is correct |
26 |
Correct |
1 ms |
384 KB |
Output is correct |
27 |
Correct |
1 ms |
256 KB |
Output is correct |
28 |
Correct |
1 ms |
256 KB |
Output is correct |
29 |
Correct |
1 ms |
256 KB |
Output is correct |
30 |
Correct |
1 ms |
256 KB |
Output is correct |
31 |
Correct |
1 ms |
384 KB |
Output is correct |
32 |
Correct |
1 ms |
256 KB |
Output is correct |
33 |
Correct |
1 ms |
384 KB |
Output is correct |
34 |
Correct |
1 ms |
384 KB |
Output is correct |
35 |
Correct |
1 ms |
384 KB |
Output is correct |
36 |
Correct |
1 ms |
384 KB |
Output is correct |
37 |
Correct |
7 ms |
384 KB |
Output is correct |
38 |
Correct |
30 ms |
896 KB |
Output is correct |
39 |
Correct |
29 ms |
896 KB |
Output is correct |
40 |
Correct |
28 ms |
896 KB |
Output is correct |
41 |
Correct |
27 ms |
896 KB |
Output is correct |
42 |
Correct |
36 ms |
1016 KB |
Output is correct |
43 |
Correct |
34 ms |
896 KB |
Output is correct |
44 |
Correct |
32 ms |
896 KB |
Output is correct |
45 |
Correct |
31 ms |
896 KB |
Output is correct |
46 |
Correct |
22 ms |
896 KB |
Output is correct |
47 |
Correct |
8 ms |
384 KB |
Output is correct |
48 |
Correct |
23 ms |
896 KB |
Output is correct |
49 |
Correct |
10 ms |
384 KB |
Output is correct |
50 |
Correct |
23 ms |
768 KB |
Output is correct |
51 |
Correct |
16 ms |
896 KB |
Output is correct |
52 |
Correct |
5 ms |
384 KB |
Output is correct |
53 |
Correct |
14 ms |
768 KB |
Output is correct |
54 |
Correct |
84 ms |
1016 KB |
Output is correct |
55 |
Correct |
69 ms |
896 KB |
Output is correct |
56 |
Correct |
64 ms |
896 KB |
Output is correct |
57 |
Correct |
55 ms |
912 KB |
Output is correct |