#include "biscuits.h"
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define ad push_back
#define lli long long
lli dp[123][20110], x;
vector<lli> a;
lli rec(lli nx, int i)
{
if(i==a.size()) return 1;
nx+=a[i];
if(nx >= x) return rec(nx/2,i+1)+rec((nx-x)/2,i+1);
return rec(nx/2,i+1);
}
long long count_tastiness(long long x, std::vector<long long> a)
{
if(x <= 10000)
{
for (int i = 0; i <= 60; i++) a.ad(0);
for (int i = 0; i < (int)a.size(); i++)
for (int j = 0; j <= 2*x+100; j++) dp[i][j]=0;
for (int i = 0; i < (int)a.size() - 1; i++)
{
a[i+1] += max(0LL, (a[i]-x)/2LL);
a[i] -= max(0LL, (a[i]-x)/2)*2LL;
}
//for(auto p : a) cout << p << " "; cout << endl;
dp[0][a[0]]=1;
if(a[0]>=x) dp[0][a[0]-x]=1;
for (int i = 1; i < (int)a.size(); i++)
{
for (int j = 0; j <= 2*x+100; j++)
{
if(dp[i-1][j]==0) continue;
int sm = j/2;
dp[i][sm+a[i]] += dp[i-1][j];
if(sm + a[i] >= x) dp[i][sm+a[i]-x] += dp[i-1][j];
}
}
lli ret = 0;
for (int i = 0; i <= 2*x+100; i++)
ret += dp[(int)a.size()-1][i];
return ret;
}
::a=a; ::x=x;
return rec(0,0);
}
Compilation message
biscuits.cpp: In function 'long long int rec(long long int, int)':
biscuits.cpp:14:6: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | if(i==a.size()) return 1;
| ~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
844 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
588 KB |
Output is correct |
4 |
Correct |
1 ms |
588 KB |
Output is correct |
5 |
Correct |
1 ms |
588 KB |
Output is correct |
6 |
Correct |
1 ms |
588 KB |
Output is correct |
7 |
Correct |
1 ms |
588 KB |
Output is correct |
8 |
Correct |
1 ms |
556 KB |
Output is correct |
9 |
Correct |
1 ms |
588 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
19 ms |
9580 KB |
Output is correct |
12 |
Correct |
1 ms |
844 KB |
Output is correct |
13 |
Correct |
1 ms |
844 KB |
Output is correct |
14 |
Correct |
2 ms |
972 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
844 KB |
Output is correct |
2 |
Correct |
1 ms |
844 KB |
Output is correct |
3 |
Correct |
1 ms |
588 KB |
Output is correct |
4 |
Correct |
1 ms |
588 KB |
Output is correct |
5 |
Correct |
1 ms |
588 KB |
Output is correct |
6 |
Correct |
1 ms |
844 KB |
Output is correct |
7 |
Correct |
1 ms |
588 KB |
Output is correct |
8 |
Correct |
1 ms |
844 KB |
Output is correct |
9 |
Correct |
1 ms |
844 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
38 ms |
18904 KB |
Output is correct |
2 |
Correct |
24 ms |
9140 KB |
Output is correct |
3 |
Correct |
30 ms |
9804 KB |
Output is correct |
4 |
Correct |
1 ms |
716 KB |
Output is correct |
5 |
Correct |
1 ms |
716 KB |
Output is correct |
6 |
Correct |
2 ms |
844 KB |
Output is correct |
7 |
Correct |
1 ms |
588 KB |
Output is correct |
8 |
Correct |
109 ms |
19276 KB |
Output is correct |
9 |
Correct |
65 ms |
10312 KB |
Output is correct |
10 |
Correct |
1 ms |
844 KB |
Output is correct |
11 |
Correct |
3 ms |
1100 KB |
Output is correct |
12 |
Correct |
15 ms |
3404 KB |
Output is correct |
13 |
Correct |
109 ms |
19328 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
844 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
588 KB |
Output is correct |
4 |
Correct |
1 ms |
588 KB |
Output is correct |
5 |
Correct |
1 ms |
588 KB |
Output is correct |
6 |
Correct |
1 ms |
588 KB |
Output is correct |
7 |
Correct |
1 ms |
588 KB |
Output is correct |
8 |
Correct |
1 ms |
556 KB |
Output is correct |
9 |
Correct |
1 ms |
588 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
19 ms |
9580 KB |
Output is correct |
12 |
Correct |
1 ms |
844 KB |
Output is correct |
13 |
Correct |
1 ms |
844 KB |
Output is correct |
14 |
Correct |
2 ms |
972 KB |
Output is correct |
15 |
Correct |
1 ms |
844 KB |
Output is correct |
16 |
Correct |
1 ms |
844 KB |
Output is correct |
17 |
Correct |
1 ms |
588 KB |
Output is correct |
18 |
Correct |
1 ms |
588 KB |
Output is correct |
19 |
Correct |
1 ms |
588 KB |
Output is correct |
20 |
Correct |
1 ms |
844 KB |
Output is correct |
21 |
Correct |
1 ms |
588 KB |
Output is correct |
22 |
Correct |
1 ms |
844 KB |
Output is correct |
23 |
Correct |
1 ms |
844 KB |
Output is correct |
24 |
Correct |
38 ms |
18904 KB |
Output is correct |
25 |
Correct |
24 ms |
9140 KB |
Output is correct |
26 |
Correct |
30 ms |
9804 KB |
Output is correct |
27 |
Correct |
1 ms |
716 KB |
Output is correct |
28 |
Correct |
1 ms |
716 KB |
Output is correct |
29 |
Correct |
2 ms |
844 KB |
Output is correct |
30 |
Correct |
1 ms |
588 KB |
Output is correct |
31 |
Correct |
109 ms |
19276 KB |
Output is correct |
32 |
Correct |
65 ms |
10312 KB |
Output is correct |
33 |
Correct |
1 ms |
844 KB |
Output is correct |
34 |
Correct |
3 ms |
1100 KB |
Output is correct |
35 |
Correct |
15 ms |
3404 KB |
Output is correct |
36 |
Correct |
109 ms |
19328 KB |
Output is correct |
37 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
38 |
Halted |
0 ms |
0 KB |
- |