#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <map>
#include <queue>
using namespace std;
const long long oo = 1000000000000000000;
long long int 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[ 5001 ], dp[ 250001 ];
vector <int> v;
bool ok( int x ) {
a[ n + 1 ] = x;
for ( int i = 1; i <= n; i ++ ) {
num = sum + x - a[ i ];
if ( num % 2 )
return false;
num /= 2;
for ( int k = num; k >= 1; k -- )
dp[ k ] = 0;
dp[ 0 ] = 1;
for ( int j = 1; j <= n + 1; j ++ ) {
if ( j == i )
continue;
for ( int k = num; k >= 0; k -- ) {
if ( dp[ k ] && k + a[ j ] <= num ) {
dp[ k + a[ j ] ] = 1;
}
}
}
if ( !dp[ num ] ) {
return false;
}
}
return true;
}
int main () {
cin >> n;
for ( int i = 1; i <= n; i ++ ) {
cin >> a[ i ], sum += a[ i ];
if ( a[ i ] % 2 )
num ++;
else
ans ++;
}
dp[ 0 ] = 1;
if ( ( num && ans ) || sum % 2 ) {
cout << "0";
return 0;
}
num = sum / 2;
for ( int i = 1; i <= n; i ++ ) {
for ( int j = num; j >= 0; j -- ) {
if ( j + a[ i ] <= num && dp[ j ] )
dp[ j + a[ i ] ] = 1;
}
}
if ( !dp[ num ] ) {
cout << 0;
return 0;
}
for ( int i = 1; i <= 1000; i ++ ) {
if ( ok( i ) )
v.push_back( i );
}
cout << v.size() << "\n";
for ( auto i : v )
cout << i << " ";
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
308 KB |
Output is correct |
2 |
Correct |
1 ms |
304 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
312 KB |
Output is correct |
5 |
Correct |
32 ms |
308 KB |
Output is correct |
6 |
Correct |
2 ms |
212 KB |
Output is correct |
7 |
Correct |
2 ms |
304 KB |
Output is correct |
8 |
Correct |
39 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
308 KB |
Output is correct |
2 |
Correct |
1 ms |
304 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
312 KB |
Output is correct |
5 |
Correct |
32 ms |
308 KB |
Output is correct |
6 |
Correct |
2 ms |
212 KB |
Output is correct |
7 |
Correct |
2 ms |
304 KB |
Output is correct |
8 |
Correct |
39 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
14 ms |
312 KB |
Output is correct |
11 |
Correct |
54 ms |
308 KB |
Output is correct |
12 |
Correct |
10 ms |
312 KB |
Output is correct |
13 |
Correct |
1 ms |
304 KB |
Output is correct |
14 |
Correct |
57 ms |
212 KB |
Output is correct |
15 |
Correct |
34 ms |
304 KB |
Output is correct |
16 |
Correct |
47 ms |
304 KB |
Output is correct |
17 |
Correct |
12 ms |
312 KB |
Output is correct |
18 |
Correct |
31 ms |
304 KB |
Output is correct |
19 |
Correct |
26 ms |
212 KB |
Output is correct |
20 |
Correct |
15 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
308 KB |
Output is correct |
2 |
Correct |
1 ms |
304 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
312 KB |
Output is correct |
5 |
Correct |
32 ms |
308 KB |
Output is correct |
6 |
Correct |
2 ms |
212 KB |
Output is correct |
7 |
Correct |
2 ms |
304 KB |
Output is correct |
8 |
Correct |
39 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
14 ms |
312 KB |
Output is correct |
11 |
Correct |
54 ms |
308 KB |
Output is correct |
12 |
Correct |
10 ms |
312 KB |
Output is correct |
13 |
Correct |
1 ms |
304 KB |
Output is correct |
14 |
Correct |
57 ms |
212 KB |
Output is correct |
15 |
Correct |
34 ms |
304 KB |
Output is correct |
16 |
Correct |
47 ms |
304 KB |
Output is correct |
17 |
Correct |
12 ms |
312 KB |
Output is correct |
18 |
Correct |
31 ms |
304 KB |
Output is correct |
19 |
Correct |
26 ms |
212 KB |
Output is correct |
20 |
Correct |
15 ms |
212 KB |
Output is correct |
21 |
Execution timed out |
1085 ms |
300 KB |
Time limit exceeded |
22 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
308 KB |
Output is correct |
2 |
Correct |
1 ms |
304 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
312 KB |
Output is correct |
5 |
Correct |
32 ms |
308 KB |
Output is correct |
6 |
Correct |
2 ms |
212 KB |
Output is correct |
7 |
Correct |
2 ms |
304 KB |
Output is correct |
8 |
Correct |
39 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
14 ms |
312 KB |
Output is correct |
11 |
Correct |
54 ms |
308 KB |
Output is correct |
12 |
Correct |
10 ms |
312 KB |
Output is correct |
13 |
Correct |
1 ms |
304 KB |
Output is correct |
14 |
Correct |
57 ms |
212 KB |
Output is correct |
15 |
Correct |
34 ms |
304 KB |
Output is correct |
16 |
Correct |
47 ms |
304 KB |
Output is correct |
17 |
Correct |
12 ms |
312 KB |
Output is correct |
18 |
Correct |
31 ms |
304 KB |
Output is correct |
19 |
Correct |
26 ms |
212 KB |
Output is correct |
20 |
Correct |
15 ms |
212 KB |
Output is correct |
21 |
Execution timed out |
1085 ms |
300 KB |
Time limit exceeded |
22 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
308 KB |
Output is correct |
2 |
Correct |
1 ms |
304 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
312 KB |
Output is correct |
5 |
Correct |
32 ms |
308 KB |
Output is correct |
6 |
Correct |
2 ms |
212 KB |
Output is correct |
7 |
Correct |
2 ms |
304 KB |
Output is correct |
8 |
Correct |
39 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
14 ms |
312 KB |
Output is correct |
11 |
Correct |
54 ms |
308 KB |
Output is correct |
12 |
Correct |
10 ms |
312 KB |
Output is correct |
13 |
Correct |
1 ms |
304 KB |
Output is correct |
14 |
Correct |
57 ms |
212 KB |
Output is correct |
15 |
Correct |
34 ms |
304 KB |
Output is correct |
16 |
Correct |
47 ms |
304 KB |
Output is correct |
17 |
Correct |
12 ms |
312 KB |
Output is correct |
18 |
Correct |
31 ms |
304 KB |
Output is correct |
19 |
Correct |
26 ms |
212 KB |
Output is correct |
20 |
Correct |
15 ms |
212 KB |
Output is correct |
21 |
Execution timed out |
1085 ms |
300 KB |
Time limit exceeded |
22 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
308 KB |
Output is correct |
2 |
Correct |
1 ms |
304 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
312 KB |
Output is correct |
5 |
Correct |
32 ms |
308 KB |
Output is correct |
6 |
Correct |
2 ms |
212 KB |
Output is correct |
7 |
Correct |
2 ms |
304 KB |
Output is correct |
8 |
Correct |
39 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
14 ms |
312 KB |
Output is correct |
11 |
Correct |
54 ms |
308 KB |
Output is correct |
12 |
Correct |
10 ms |
312 KB |
Output is correct |
13 |
Correct |
1 ms |
304 KB |
Output is correct |
14 |
Correct |
57 ms |
212 KB |
Output is correct |
15 |
Correct |
34 ms |
304 KB |
Output is correct |
16 |
Correct |
47 ms |
304 KB |
Output is correct |
17 |
Correct |
12 ms |
312 KB |
Output is correct |
18 |
Correct |
31 ms |
304 KB |
Output is correct |
19 |
Correct |
26 ms |
212 KB |
Output is correct |
20 |
Correct |
15 ms |
212 KB |
Output is correct |
21 |
Execution timed out |
1085 ms |
300 KB |
Time limit exceeded |
22 |
Halted |
0 ms |
0 KB |
- |