# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
386230 | 2021-04-06T07:27:38 Z | patrikpavic2 | Bootfall (IZhO17_bootfall) | C++17 | 264 ms | 35220 KB |
#include <cstdio> #include <cstdlib> #include <bitset> #include <vector> #include <algorithm> #define PB push_back using namespace std; const int N = 505; const int OFF = N * N; bitset < 2 * OFF > dp[N]; bitset < 2 * OFF > pres; int n, sz = 1, A[N], mogu = 0; void solve(int l, int r){ if(l > r) return; if(l == r){ pres = pres & dp[sz - 1]; if(!l){ dp[sz] = (dp[sz - 1] << A[0]) | (dp[sz - 1] >> A[0]); mogu = dp[sz][OFF]; } return; } int mid = (l + r) / 2; if(mid + 1 <= r){ for(int i = l;i <= mid;i++){ dp[sz] = (dp[sz - 1] << A[i]) | (dp[sz - 1] >> A[i]); sz++; } solve(mid + 1, r); sz -= mid - l + 1; } if(l <= mid){ for(int i = mid + 1;i <= r;i++){ dp[sz] = (dp[sz - 1] << A[i]) | (dp[sz - 1] >> A[i]); sz++; } solve(l, mid); sz -= r - mid; } } vector < int > sol; int main(){ dp[0][OFF] = 1; for(int i = 0;i < 2 * OFF;i++) pres[i] = 1; scanf("%d", &n); for(int i = 0;i < n;i++){ scanf("%d", A + i); } solve(0, n - 1); if(!mogu){ printf("0\n"); return 0; } for(int i = 0;i < 2 * OFF;i++) if(pres[i]) sol.PB(abs(i - OFF)); sort(sol.begin(), sol.end()); sol.erase(unique(sol.begin(), sol.end()), sol.end()); printf("%d\n", (int)sol.size()); for(int x : sol) printf("%d ", x); printf("\n"); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1132 KB | Output is correct |
2 | Correct | 4 ms | 1516 KB | Output is correct |
3 | Correct | 3 ms | 1132 KB | Output is correct |
4 | Correct | 3 ms | 1132 KB | Output is correct |
5 | Correct | 5 ms | 2028 KB | Output is correct |
6 | Correct | 4 ms | 1664 KB | Output is correct |
7 | Correct | 4 ms | 1536 KB | Output is correct |
8 | Correct | 5 ms | 2028 KB | Output is correct |
9 | Correct | 5 ms | 1900 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1132 KB | Output is correct |
2 | Correct | 4 ms | 1516 KB | Output is correct |
3 | Correct | 3 ms | 1132 KB | Output is correct |
4 | Correct | 3 ms | 1132 KB | Output is correct |
5 | Correct | 5 ms | 2028 KB | Output is correct |
6 | Correct | 4 ms | 1664 KB | Output is correct |
7 | Correct | 4 ms | 1536 KB | Output is correct |
8 | Correct | 5 ms | 2028 KB | Output is correct |
9 | Correct | 5 ms | 1900 KB | Output is correct |
10 | Correct | 10 ms | 3308 KB | Output is correct |
11 | Correct | 11 ms | 3308 KB | Output is correct |
12 | Correct | 10 ms | 3308 KB | Output is correct |
13 | Correct | 9 ms | 3180 KB | Output is correct |
14 | Correct | 10 ms | 3328 KB | Output is correct |
15 | Correct | 10 ms | 3180 KB | Output is correct |
16 | Correct | 10 ms | 3308 KB | Output is correct |
17 | Correct | 9 ms | 2668 KB | Output is correct |
18 | Correct | 9 ms | 3052 KB | Output is correct |
19 | Correct | 9 ms | 3180 KB | Output is correct |
20 | Correct | 10 ms | 3308 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1132 KB | Output is correct |
2 | Correct | 4 ms | 1516 KB | Output is correct |
3 | Correct | 3 ms | 1132 KB | Output is correct |
4 | Correct | 3 ms | 1132 KB | Output is correct |
5 | Correct | 5 ms | 2028 KB | Output is correct |
6 | Correct | 4 ms | 1664 KB | Output is correct |
7 | Correct | 4 ms | 1536 KB | Output is correct |
8 | Correct | 5 ms | 2028 KB | Output is correct |
9 | Correct | 5 ms | 1900 KB | Output is correct |
10 | Correct | 10 ms | 3308 KB | Output is correct |
11 | Correct | 11 ms | 3308 KB | Output is correct |
12 | Correct | 10 ms | 3308 KB | Output is correct |
13 | Correct | 9 ms | 3180 KB | Output is correct |
14 | Correct | 10 ms | 3328 KB | Output is correct |
15 | Correct | 10 ms | 3180 KB | Output is correct |
16 | Correct | 10 ms | 3308 KB | Output is correct |
17 | Correct | 9 ms | 2668 KB | Output is correct |
18 | Correct | 9 ms | 3052 KB | Output is correct |
19 | Correct | 9 ms | 3180 KB | Output is correct |
20 | Correct | 10 ms | 3308 KB | Output is correct |
21 | Correct | 22 ms | 5740 KB | Output is correct |
22 | Correct | 26 ms | 6508 KB | Output is correct |
23 | Correct | 17 ms | 4844 KB | Output is correct |
24 | Correct | 33 ms | 7868 KB | Output is correct |
25 | Correct | 36 ms | 7788 KB | Output is correct |
26 | Correct | 36 ms | 8172 KB | Output is correct |
27 | Correct | 36 ms | 8172 KB | Output is correct |
28 | Correct | 36 ms | 8172 KB | Output is correct |
29 | Correct | 35 ms | 8172 KB | Output is correct |
30 | Correct | 45 ms | 8172 KB | Output is correct |
31 | Correct | 36 ms | 8172 KB | Output is correct |
32 | Correct | 36 ms | 8172 KB | Output is correct |
33 | Correct | 45 ms | 8172 KB | Output is correct |
34 | Correct | 35 ms | 8172 KB | Output is correct |
35 | Correct | 35 ms | 8176 KB | Output is correct |
36 | Correct | 39 ms | 8116 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1132 KB | Output is correct |
2 | Correct | 4 ms | 1516 KB | Output is correct |
3 | Correct | 3 ms | 1132 KB | Output is correct |
4 | Correct | 3 ms | 1132 KB | Output is correct |
5 | Correct | 5 ms | 2028 KB | Output is correct |
6 | Correct | 4 ms | 1664 KB | Output is correct |
7 | Correct | 4 ms | 1536 KB | Output is correct |
8 | Correct | 5 ms | 2028 KB | Output is correct |
9 | Correct | 5 ms | 1900 KB | Output is correct |
10 | Correct | 10 ms | 3308 KB | Output is correct |
11 | Correct | 11 ms | 3308 KB | Output is correct |
12 | Correct | 10 ms | 3308 KB | Output is correct |
13 | Correct | 9 ms | 3180 KB | Output is correct |
14 | Correct | 10 ms | 3328 KB | Output is correct |
15 | Correct | 10 ms | 3180 KB | Output is correct |
16 | Correct | 10 ms | 3308 KB | Output is correct |
17 | Correct | 9 ms | 2668 KB | Output is correct |
18 | Correct | 9 ms | 3052 KB | Output is correct |
19 | Correct | 9 ms | 3180 KB | Output is correct |
20 | Correct | 10 ms | 3308 KB | Output is correct |
21 | Correct | 22 ms | 5740 KB | Output is correct |
22 | Correct | 26 ms | 6508 KB | Output is correct |
23 | Correct | 17 ms | 4844 KB | Output is correct |
24 | Correct | 33 ms | 7868 KB | Output is correct |
25 | Correct | 36 ms | 7788 KB | Output is correct |
26 | Correct | 36 ms | 8172 KB | Output is correct |
27 | Correct | 36 ms | 8172 KB | Output is correct |
28 | Correct | 36 ms | 8172 KB | Output is correct |
29 | Correct | 35 ms | 8172 KB | Output is correct |
30 | Correct | 45 ms | 8172 KB | Output is correct |
31 | Correct | 36 ms | 8172 KB | Output is correct |
32 | Correct | 36 ms | 8172 KB | Output is correct |
33 | Correct | 45 ms | 8172 KB | Output is correct |
34 | Correct | 35 ms | 8172 KB | Output is correct |
35 | Correct | 35 ms | 8176 KB | Output is correct |
36 | Correct | 39 ms | 8116 KB | Output is correct |
37 | Correct | 89 ms | 14796 KB | Output is correct |
38 | Correct | 80 ms | 14828 KB | Output is correct |
39 | Correct | 99 ms | 17516 KB | Output is correct |
40 | Correct | 117 ms | 19436 KB | Output is correct |
41 | Correct | 109 ms | 19096 KB | Output is correct |
42 | Correct | 99 ms | 18028 KB | Output is correct |
43 | Correct | 104 ms | 17768 KB | Output is correct |
44 | Correct | 105 ms | 18044 KB | Output is correct |
45 | Correct | 109 ms | 18152 KB | Output is correct |
46 | Correct | 107 ms | 19052 KB | Output is correct |
47 | Correct | 106 ms | 18028 KB | Output is correct |
48 | Correct | 99 ms | 18028 KB | Output is correct |
49 | Correct | 97 ms | 17772 KB | Output is correct |
50 | Correct | 101 ms | 18028 KB | Output is correct |
51 | Correct | 95 ms | 17660 KB | Output is correct |
52 | Correct | 116 ms | 19560 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1132 KB | Output is correct |
2 | Correct | 4 ms | 1516 KB | Output is correct |
3 | Correct | 3 ms | 1132 KB | Output is correct |
4 | Correct | 3 ms | 1132 KB | Output is correct |
5 | Correct | 5 ms | 2028 KB | Output is correct |
6 | Correct | 4 ms | 1664 KB | Output is correct |
7 | Correct | 4 ms | 1536 KB | Output is correct |
8 | Correct | 5 ms | 2028 KB | Output is correct |
9 | Correct | 5 ms | 1900 KB | Output is correct |
10 | Correct | 10 ms | 3308 KB | Output is correct |
11 | Correct | 11 ms | 3308 KB | Output is correct |
12 | Correct | 10 ms | 3308 KB | Output is correct |
13 | Correct | 9 ms | 3180 KB | Output is correct |
14 | Correct | 10 ms | 3328 KB | Output is correct |
15 | Correct | 10 ms | 3180 KB | Output is correct |
16 | Correct | 10 ms | 3308 KB | Output is correct |
17 | Correct | 9 ms | 2668 KB | Output is correct |
18 | Correct | 9 ms | 3052 KB | Output is correct |
19 | Correct | 9 ms | 3180 KB | Output is correct |
20 | Correct | 10 ms | 3308 KB | Output is correct |
21 | Correct | 22 ms | 5740 KB | Output is correct |
22 | Correct | 26 ms | 6508 KB | Output is correct |
23 | Correct | 17 ms | 4844 KB | Output is correct |
24 | Correct | 33 ms | 7868 KB | Output is correct |
25 | Correct | 36 ms | 7788 KB | Output is correct |
26 | Correct | 36 ms | 8172 KB | Output is correct |
27 | Correct | 36 ms | 8172 KB | Output is correct |
28 | Correct | 36 ms | 8172 KB | Output is correct |
29 | Correct | 35 ms | 8172 KB | Output is correct |
30 | Correct | 45 ms | 8172 KB | Output is correct |
31 | Correct | 36 ms | 8172 KB | Output is correct |
32 | Correct | 36 ms | 8172 KB | Output is correct |
33 | Correct | 45 ms | 8172 KB | Output is correct |
34 | Correct | 35 ms | 8172 KB | Output is correct |
35 | Correct | 35 ms | 8176 KB | Output is correct |
36 | Correct | 39 ms | 8116 KB | Output is correct |
37 | Correct | 89 ms | 14796 KB | Output is correct |
38 | Correct | 80 ms | 14828 KB | Output is correct |
39 | Correct | 99 ms | 17516 KB | Output is correct |
40 | Correct | 117 ms | 19436 KB | Output is correct |
41 | Correct | 109 ms | 19096 KB | Output is correct |
42 | Correct | 99 ms | 18028 KB | Output is correct |
43 | Correct | 104 ms | 17768 KB | Output is correct |
44 | Correct | 105 ms | 18044 KB | Output is correct |
45 | Correct | 109 ms | 18152 KB | Output is correct |
46 | Correct | 107 ms | 19052 KB | Output is correct |
47 | Correct | 106 ms | 18028 KB | Output is correct |
48 | Correct | 99 ms | 18028 KB | Output is correct |
49 | Correct | 97 ms | 17772 KB | Output is correct |
50 | Correct | 101 ms | 18028 KB | Output is correct |
51 | Correct | 95 ms | 17660 KB | Output is correct |
52 | Correct | 116 ms | 19560 KB | Output is correct |
53 | Correct | 124 ms | 21356 KB | Output is correct |
54 | Correct | 159 ms | 24680 KB | Output is correct |
55 | Correct | 164 ms | 24936 KB | Output is correct |
56 | Correct | 131 ms | 21792 KB | Output is correct |
57 | Correct | 156 ms | 25060 KB | Output is correct |
58 | Correct | 153 ms | 24680 KB | Output is correct |
59 | Correct | 153 ms | 24828 KB | Output is correct |
60 | Correct | 140 ms | 24044 KB | Output is correct |
61 | Correct | 155 ms | 24804 KB | Output is correct |
62 | Correct | 149 ms | 23012 KB | Output is correct |
63 | Correct | 156 ms | 23012 KB | Output is correct |
64 | Correct | 151 ms | 22604 KB | Output is correct |
65 | Correct | 128 ms | 21944 KB | Output is correct |
66 | Correct | 135 ms | 21740 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1132 KB | Output is correct |
2 | Correct | 4 ms | 1516 KB | Output is correct |
3 | Correct | 3 ms | 1132 KB | Output is correct |
4 | Correct | 3 ms | 1132 KB | Output is correct |
5 | Correct | 5 ms | 2028 KB | Output is correct |
6 | Correct | 4 ms | 1664 KB | Output is correct |
7 | Correct | 4 ms | 1536 KB | Output is correct |
8 | Correct | 5 ms | 2028 KB | Output is correct |
9 | Correct | 5 ms | 1900 KB | Output is correct |
10 | Correct | 10 ms | 3308 KB | Output is correct |
11 | Correct | 11 ms | 3308 KB | Output is correct |
12 | Correct | 10 ms | 3308 KB | Output is correct |
13 | Correct | 9 ms | 3180 KB | Output is correct |
14 | Correct | 10 ms | 3328 KB | Output is correct |
15 | Correct | 10 ms | 3180 KB | Output is correct |
16 | Correct | 10 ms | 3308 KB | Output is correct |
17 | Correct | 9 ms | 2668 KB | Output is correct |
18 | Correct | 9 ms | 3052 KB | Output is correct |
19 | Correct | 9 ms | 3180 KB | Output is correct |
20 | Correct | 10 ms | 3308 KB | Output is correct |
21 | Correct | 22 ms | 5740 KB | Output is correct |
22 | Correct | 26 ms | 6508 KB | Output is correct |
23 | Correct | 17 ms | 4844 KB | Output is correct |
24 | Correct | 33 ms | 7868 KB | Output is correct |
25 | Correct | 36 ms | 7788 KB | Output is correct |
26 | Correct | 36 ms | 8172 KB | Output is correct |
27 | Correct | 36 ms | 8172 KB | Output is correct |
28 | Correct | 36 ms | 8172 KB | Output is correct |
29 | Correct | 35 ms | 8172 KB | Output is correct |
30 | Correct | 45 ms | 8172 KB | Output is correct |
31 | Correct | 36 ms | 8172 KB | Output is correct |
32 | Correct | 36 ms | 8172 KB | Output is correct |
33 | Correct | 45 ms | 8172 KB | Output is correct |
34 | Correct | 35 ms | 8172 KB | Output is correct |
35 | Correct | 35 ms | 8176 KB | Output is correct |
36 | Correct | 39 ms | 8116 KB | Output is correct |
37 | Correct | 89 ms | 14796 KB | Output is correct |
38 | Correct | 80 ms | 14828 KB | Output is correct |
39 | Correct | 99 ms | 17516 KB | Output is correct |
40 | Correct | 117 ms | 19436 KB | Output is correct |
41 | Correct | 109 ms | 19096 KB | Output is correct |
42 | Correct | 99 ms | 18028 KB | Output is correct |
43 | Correct | 104 ms | 17768 KB | Output is correct |
44 | Correct | 105 ms | 18044 KB | Output is correct |
45 | Correct | 109 ms | 18152 KB | Output is correct |
46 | Correct | 107 ms | 19052 KB | Output is correct |
47 | Correct | 106 ms | 18028 KB | Output is correct |
48 | Correct | 99 ms | 18028 KB | Output is correct |
49 | Correct | 97 ms | 17772 KB | Output is correct |
50 | Correct | 101 ms | 18028 KB | Output is correct |
51 | Correct | 95 ms | 17660 KB | Output is correct |
52 | Correct | 116 ms | 19560 KB | Output is correct |
53 | Correct | 124 ms | 21356 KB | Output is correct |
54 | Correct | 159 ms | 24680 KB | Output is correct |
55 | Correct | 164 ms | 24936 KB | Output is correct |
56 | Correct | 131 ms | 21792 KB | Output is correct |
57 | Correct | 156 ms | 25060 KB | Output is correct |
58 | Correct | 153 ms | 24680 KB | Output is correct |
59 | Correct | 153 ms | 24828 KB | Output is correct |
60 | Correct | 140 ms | 24044 KB | Output is correct |
61 | Correct | 155 ms | 24804 KB | Output is correct |
62 | Correct | 149 ms | 23012 KB | Output is correct |
63 | Correct | 156 ms | 23012 KB | Output is correct |
64 | Correct | 151 ms | 22604 KB | Output is correct |
65 | Correct | 128 ms | 21944 KB | Output is correct |
66 | Correct | 135 ms | 21740 KB | Output is correct |
67 | Correct | 179 ms | 27880 KB | Output is correct |
68 | Correct | 215 ms | 33388 KB | Output is correct |
69 | Correct | 240 ms | 35040 KB | Output is correct |
70 | Correct | 225 ms | 34456 KB | Output is correct |
71 | Correct | 227 ms | 34456 KB | Output is correct |
72 | Correct | 209 ms | 33452 KB | Output is correct |
73 | Correct | 213 ms | 33516 KB | Output is correct |
74 | Correct | 264 ms | 35040 KB | Output is correct |
75 | Correct | 234 ms | 34784 KB | Output is correct |
76 | Correct | 242 ms | 35092 KB | Output is correct |
77 | Correct | 249 ms | 35220 KB | Output is correct |