#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <map>
#include <queue>
#define int long long
using namespace std;
const long long oo = 1000000000000000000;
long long sum, ans = 0, mx = 0, mn = 1000000000, num, pos;
/*
ViHHiPuh
(( `'-""``""-'` ))
)-__-_.._-__-(
/ --- (o _ o) --- \
\ .-* ( .0. ) *-. /
_'-. ,_ '=' _, .-'_
/ `;#'#'# - #'#'#;` \
\_)) -----'#'----- ((_/
# --------- #
'# ------- ------ #'
/..-'# ------- #'-.\
_\...-\'# -- #'/-.../_
((____)- '#' -(____))
cout << fixed << setprecision(6) << x;
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
freopen ( "sum.in", "r", stdin )
*/
int n, a[ 10001 ], dp[ 2500001 ], mp[ 2500001 ], mpp[ 2500001 ];
vector <int> v;
int mod = 1e9 + 7;
main () {
cin >> n;
dp[ 0 ] = 1;
for ( int i = 1; i <= n; i ++ ) {
cin >> a[ i ];
for ( int j = sum; j >= 0; j -- ) {
dp[ j + a[ i ] ] += dp[ j ];
if ( dp[ j + a[ i ] ] >= mod )
dp[ j + a[ i ] ] -= mod;
}
sum += a[ i ];
}
if ( sum % 2 || !dp[ sum / 2 ] ) {
cout << 0;
return 0;
}
for ( int i = 1; i <= n; i ++ ) {
for ( int j = 0; j <= sum; j ++ )
mp[ j ] = dp[ j ];
for ( int j = 0; j <= sum; j ++ ) {
if ( a[ i ] + j > sum )
break;
mp[ j + a[ i ] ] += mod - mp[ j ];
if ( mp[ j + a[ i ] ] >= mod )
mp[ j + a[ i ] ] -= mod;
}
num = sum - a[ i ];
for ( int j = 1; j <= num; j ++ ) {
if ( ( num + j ) % 2 )
continue;
if ( mp[ ( num + j ) / 2 - j ] )
mpp[ j ] ++;
}
}
for ( int i = 1; i <= sum; i ++ ) {
if ( mpp[ i ] == n )
v.push_back( i );
}
cout << v.size() << "\n";
for ( auto i : v )
cout << i << " ";
}
/*
6
3 6 4 5 1 2
*/
Compilation message
bootfall.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
50 | main () {
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
2 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
2 ms |
468 KB |
Output is correct |
25 |
Correct |
3 ms |
596 KB |
Output is correct |
26 |
Correct |
4 ms |
596 KB |
Output is correct |
27 |
Correct |
4 ms |
468 KB |
Output is correct |
28 |
Correct |
4 ms |
468 KB |
Output is correct |
29 |
Correct |
4 ms |
468 KB |
Output is correct |
30 |
Correct |
2 ms |
340 KB |
Output is correct |
31 |
Correct |
3 ms |
468 KB |
Output is correct |
32 |
Correct |
2 ms |
468 KB |
Output is correct |
33 |
Correct |
4 ms |
552 KB |
Output is correct |
34 |
Correct |
5 ms |
560 KB |
Output is correct |
35 |
Correct |
4 ms |
468 KB |
Output is correct |
36 |
Correct |
2 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
2 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
2 ms |
468 KB |
Output is correct |
25 |
Correct |
3 ms |
596 KB |
Output is correct |
26 |
Correct |
4 ms |
596 KB |
Output is correct |
27 |
Correct |
4 ms |
468 KB |
Output is correct |
28 |
Correct |
4 ms |
468 KB |
Output is correct |
29 |
Correct |
4 ms |
468 KB |
Output is correct |
30 |
Correct |
2 ms |
340 KB |
Output is correct |
31 |
Correct |
3 ms |
468 KB |
Output is correct |
32 |
Correct |
2 ms |
468 KB |
Output is correct |
33 |
Correct |
4 ms |
552 KB |
Output is correct |
34 |
Correct |
5 ms |
560 KB |
Output is correct |
35 |
Correct |
4 ms |
468 KB |
Output is correct |
36 |
Correct |
2 ms |
468 KB |
Output is correct |
37 |
Correct |
14 ms |
1032 KB |
Output is correct |
38 |
Correct |
13 ms |
980 KB |
Output is correct |
39 |
Correct |
51 ms |
1760 KB |
Output is correct |
40 |
Correct |
30 ms |
1344 KB |
Output is correct |
41 |
Correct |
63 ms |
1876 KB |
Output is correct |
42 |
Correct |
25 ms |
1284 KB |
Output is correct |
43 |
Correct |
43 ms |
2000 KB |
Output is correct |
44 |
Correct |
50 ms |
2016 KB |
Output is correct |
45 |
Correct |
48 ms |
2032 KB |
Output is correct |
46 |
Correct |
28 ms |
1044 KB |
Output is correct |
47 |
Correct |
27 ms |
1368 KB |
Output is correct |
48 |
Correct |
52 ms |
2144 KB |
Output is correct |
49 |
Correct |
52 ms |
1768 KB |
Output is correct |
50 |
Correct |
27 ms |
1348 KB |
Output is correct |
51 |
Correct |
5 ms |
468 KB |
Output is correct |
52 |
Correct |
63 ms |
2468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
2 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
2 ms |
468 KB |
Output is correct |
25 |
Correct |
3 ms |
596 KB |
Output is correct |
26 |
Correct |
4 ms |
596 KB |
Output is correct |
27 |
Correct |
4 ms |
468 KB |
Output is correct |
28 |
Correct |
4 ms |
468 KB |
Output is correct |
29 |
Correct |
4 ms |
468 KB |
Output is correct |
30 |
Correct |
2 ms |
340 KB |
Output is correct |
31 |
Correct |
3 ms |
468 KB |
Output is correct |
32 |
Correct |
2 ms |
468 KB |
Output is correct |
33 |
Correct |
4 ms |
552 KB |
Output is correct |
34 |
Correct |
5 ms |
560 KB |
Output is correct |
35 |
Correct |
4 ms |
468 KB |
Output is correct |
36 |
Correct |
2 ms |
468 KB |
Output is correct |
37 |
Correct |
14 ms |
1032 KB |
Output is correct |
38 |
Correct |
13 ms |
980 KB |
Output is correct |
39 |
Correct |
51 ms |
1760 KB |
Output is correct |
40 |
Correct |
30 ms |
1344 KB |
Output is correct |
41 |
Correct |
63 ms |
1876 KB |
Output is correct |
42 |
Correct |
25 ms |
1284 KB |
Output is correct |
43 |
Correct |
43 ms |
2000 KB |
Output is correct |
44 |
Correct |
50 ms |
2016 KB |
Output is correct |
45 |
Correct |
48 ms |
2032 KB |
Output is correct |
46 |
Correct |
28 ms |
1044 KB |
Output is correct |
47 |
Correct |
27 ms |
1368 KB |
Output is correct |
48 |
Correct |
52 ms |
2144 KB |
Output is correct |
49 |
Correct |
52 ms |
1768 KB |
Output is correct |
50 |
Correct |
27 ms |
1348 KB |
Output is correct |
51 |
Correct |
5 ms |
468 KB |
Output is correct |
52 |
Correct |
63 ms |
2468 KB |
Output is correct |
53 |
Correct |
45 ms |
1776 KB |
Output is correct |
54 |
Correct |
67 ms |
2124 KB |
Output is correct |
55 |
Correct |
125 ms |
3780 KB |
Output is correct |
56 |
Correct |
59 ms |
2120 KB |
Output is correct |
57 |
Correct |
132 ms |
3812 KB |
Output is correct |
58 |
Correct |
72 ms |
2264 KB |
Output is correct |
59 |
Correct |
85 ms |
2752 KB |
Output is correct |
60 |
Correct |
10 ms |
688 KB |
Output is correct |
61 |
Correct |
94 ms |
2956 KB |
Output is correct |
62 |
Correct |
97 ms |
3312 KB |
Output is correct |
63 |
Correct |
109 ms |
3496 KB |
Output is correct |
64 |
Correct |
102 ms |
3524 KB |
Output is correct |
65 |
Correct |
54 ms |
1436 KB |
Output is correct |
66 |
Correct |
57 ms |
1696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
2 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
2 ms |
468 KB |
Output is correct |
25 |
Correct |
3 ms |
596 KB |
Output is correct |
26 |
Correct |
4 ms |
596 KB |
Output is correct |
27 |
Correct |
4 ms |
468 KB |
Output is correct |
28 |
Correct |
4 ms |
468 KB |
Output is correct |
29 |
Correct |
4 ms |
468 KB |
Output is correct |
30 |
Correct |
2 ms |
340 KB |
Output is correct |
31 |
Correct |
3 ms |
468 KB |
Output is correct |
32 |
Correct |
2 ms |
468 KB |
Output is correct |
33 |
Correct |
4 ms |
552 KB |
Output is correct |
34 |
Correct |
5 ms |
560 KB |
Output is correct |
35 |
Correct |
4 ms |
468 KB |
Output is correct |
36 |
Correct |
2 ms |
468 KB |
Output is correct |
37 |
Correct |
14 ms |
1032 KB |
Output is correct |
38 |
Correct |
13 ms |
980 KB |
Output is correct |
39 |
Correct |
51 ms |
1760 KB |
Output is correct |
40 |
Correct |
30 ms |
1344 KB |
Output is correct |
41 |
Correct |
63 ms |
1876 KB |
Output is correct |
42 |
Correct |
25 ms |
1284 KB |
Output is correct |
43 |
Correct |
43 ms |
2000 KB |
Output is correct |
44 |
Correct |
50 ms |
2016 KB |
Output is correct |
45 |
Correct |
48 ms |
2032 KB |
Output is correct |
46 |
Correct |
28 ms |
1044 KB |
Output is correct |
47 |
Correct |
27 ms |
1368 KB |
Output is correct |
48 |
Correct |
52 ms |
2144 KB |
Output is correct |
49 |
Correct |
52 ms |
1768 KB |
Output is correct |
50 |
Correct |
27 ms |
1348 KB |
Output is correct |
51 |
Correct |
5 ms |
468 KB |
Output is correct |
52 |
Correct |
63 ms |
2468 KB |
Output is correct |
53 |
Correct |
45 ms |
1776 KB |
Output is correct |
54 |
Correct |
67 ms |
2124 KB |
Output is correct |
55 |
Correct |
125 ms |
3780 KB |
Output is correct |
56 |
Correct |
59 ms |
2120 KB |
Output is correct |
57 |
Correct |
132 ms |
3812 KB |
Output is correct |
58 |
Correct |
72 ms |
2264 KB |
Output is correct |
59 |
Correct |
85 ms |
2752 KB |
Output is correct |
60 |
Correct |
10 ms |
688 KB |
Output is correct |
61 |
Correct |
94 ms |
2956 KB |
Output is correct |
62 |
Correct |
97 ms |
3312 KB |
Output is correct |
63 |
Correct |
109 ms |
3496 KB |
Output is correct |
64 |
Correct |
102 ms |
3524 KB |
Output is correct |
65 |
Correct |
54 ms |
1436 KB |
Output is correct |
66 |
Correct |
57 ms |
1696 KB |
Output is correct |
67 |
Correct |
99 ms |
2828 KB |
Output is correct |
68 |
Correct |
30 ms |
1184 KB |
Output is correct |
69 |
Correct |
346 ms |
6748 KB |
Output is correct |
70 |
Correct |
197 ms |
4328 KB |
Output is correct |
71 |
Correct |
194 ms |
4240 KB |
Output is correct |
72 |
Correct |
192 ms |
3248 KB |
Output is correct |
73 |
Correct |
191 ms |
3324 KB |
Output is correct |
74 |
Correct |
351 ms |
7228 KB |
Output is correct |
75 |
Correct |
269 ms |
5700 KB |
Output is correct |
76 |
Correct |
399 ms |
7544 KB |
Output is correct |
77 |
Correct |
388 ms |
7584 KB |
Output is correct |