#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;
vector<map<long long, long long> > dp;
vector<int> v(60);
long long X;
long long getDP(int bit, long long cnt){
cnt += v[bit];
if(bit == 60) return 1;
if(dp[bit][cnt] != 0) return dp[bit][cnt];
dp[bit][cnt] = getDP(bit + 1, cnt / 2);
if(cnt >= X) dp[bit][cnt] += getDP(bit + 1, (cnt - X) / 2);
// printf("dp[%d][%lld] = %d\n", bit, cnt, dp[bit][cnt]);
return dp[bit][cnt];
}
long long sub1(long long x, vector<long long> a){
int ini = 0;
long long ans = 1;
v = vector<int> (60, 0);
for(ini = 0; ini < 60;){
int fim = ini;
long long sobra = 0;
long long num = 0;
long long cnt = 0;
while(fim < 60){
long long val = 0;
if(fim < a.size()) val = a[fim];
long long tot = val + sobra;
sobra = tot / 2;
if(tot % 2 == 1) num |= (1LL << cnt);
fim++;
cnt++;
if(sobra == 0) break;
}
ans *= num + 1;
ini = fim;
}
return ans;
}
long long count_tastiness(long long x, vector<long long> a) {
if(x == 1) return sub1(x, a);
X = x;
v = vector<int> (60, 0);
dp = vector<map<long long, long long> > (60);
for(int i = 0; i < a.size(); i++)
v[i] = a[i];
return getDP(0, 0);
}
Compilation message
biscuits.cpp: In function 'long long int sub1(long long int, std::vector<long long int>)':
biscuits.cpp:30:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | if(fim < a.size()) val = a[fim];
| ~~~~^~~~~~~~~~
biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:49:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(int i = 0; i < a.size(); i++)
| ~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 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 |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
2 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
17 ms |
2244 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
668 ms |
4312 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 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 |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
2 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
0 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 |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
0 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Incorrect |
17 ms |
2244 KB |
Output isn't correct |
25 |
Halted |
0 ms |
0 KB |
- |