# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
434545 | 2021-06-21T11:52:34 Z | arayi | Packing Biscuits (IOI20_biscuits) | C++17 | 109 ms | 19328 KB |
#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
# | Verdict | Execution time | Memory | 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 |
# | Verdict | Execution time | Memory | 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 |
# | Verdict | Execution time | Memory | 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 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 332 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | 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 | - |