#include <bits/stdc++.h>
#define int long long
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define ff first
#define ss second
#define dbg(x) cerr << #x << " = " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vvi = vt< vt<int> >;
const int N = 1e6 + 5, mod = 1e9 + 7, inf = 1e18 + 7, B = 500, LIM = (1ll << 60);
const double eps = 1e-6;
template<class Iterator> std::ostream& print_range(std::ostream& os, Iterator begin, Iterator end) {
os << "{";
for (auto it = begin; it != end; os << *it++) if (it != begin) os << ", ";
return os << "}";
}
template<class X> std::ostream& operator<<(std::ostream& os, const std::vector<X>& vec) {
return print_range(os, all(vec));
}
int dp[N];
void solve () {
int n;
cin >> n;
vt<int> a(n + 1);
int sum = 0;
for (int i = 1; i <= n; i++) cin >> a[i], sum += a[i];
if (n & 1) cout << "0\n", exit(0);
set<int> ans;
vt<int> used(N, 0);
dp[0] = 1;
for (int val = 1; val <= 4000; val++) {
for (int i = 1; i <= n; i++) {
int x = a[i], s = sum - a[i];
a[i] = val;
s += a[i];
if (s & 1) {
a[i] = x;
continue;
}
for (int j = 1; j <= n; j++) {
for (int w = s - a[j]; w >= 0; w--) {
if (dp[w] == 1) dp[w + a[j]] = 1;
}
}
if (dp[s / 2] == 1) {
used[val]++;
if (used[val] >= n) ans.insert(val);
}
a[i] = x;
for (int j = 1; j <= s; j++) dp[j] = 0;
}
}
cout << sz(ans) << '\n';
for (auto x: ans) cout << x << ' ';
cout << '\n';
}
bool testcases = 0;
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int test = 1;
if (testcases) cin >> test;
for (int cs = 1; cs <= test; cs++) {
solve();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
8164 KB |
Output is correct |
2 |
Correct |
92 ms |
8176 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
50 ms |
8140 KB |
Output is correct |
5 |
Correct |
804 ms |
8164 KB |
Output is correct |
6 |
Correct |
187 ms |
8168 KB |
Output is correct |
7 |
Correct |
112 ms |
8172 KB |
Output is correct |
8 |
Correct |
893 ms |
8172 KB |
Output is correct |
9 |
Correct |
420 ms |
8152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
8164 KB |
Output is correct |
2 |
Correct |
92 ms |
8176 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
50 ms |
8140 KB |
Output is correct |
5 |
Correct |
804 ms |
8164 KB |
Output is correct |
6 |
Correct |
187 ms |
8168 KB |
Output is correct |
7 |
Correct |
112 ms |
8172 KB |
Output is correct |
8 |
Correct |
893 ms |
8172 KB |
Output is correct |
9 |
Correct |
420 ms |
8152 KB |
Output is correct |
10 |
Execution timed out |
1094 ms |
8280 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
8164 KB |
Output is correct |
2 |
Correct |
92 ms |
8176 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
50 ms |
8140 KB |
Output is correct |
5 |
Correct |
804 ms |
8164 KB |
Output is correct |
6 |
Correct |
187 ms |
8168 KB |
Output is correct |
7 |
Correct |
112 ms |
8172 KB |
Output is correct |
8 |
Correct |
893 ms |
8172 KB |
Output is correct |
9 |
Correct |
420 ms |
8152 KB |
Output is correct |
10 |
Execution timed out |
1094 ms |
8280 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
8164 KB |
Output is correct |
2 |
Correct |
92 ms |
8176 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
50 ms |
8140 KB |
Output is correct |
5 |
Correct |
804 ms |
8164 KB |
Output is correct |
6 |
Correct |
187 ms |
8168 KB |
Output is correct |
7 |
Correct |
112 ms |
8172 KB |
Output is correct |
8 |
Correct |
893 ms |
8172 KB |
Output is correct |
9 |
Correct |
420 ms |
8152 KB |
Output is correct |
10 |
Execution timed out |
1094 ms |
8280 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
8164 KB |
Output is correct |
2 |
Correct |
92 ms |
8176 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
50 ms |
8140 KB |
Output is correct |
5 |
Correct |
804 ms |
8164 KB |
Output is correct |
6 |
Correct |
187 ms |
8168 KB |
Output is correct |
7 |
Correct |
112 ms |
8172 KB |
Output is correct |
8 |
Correct |
893 ms |
8172 KB |
Output is correct |
9 |
Correct |
420 ms |
8152 KB |
Output is correct |
10 |
Execution timed out |
1094 ms |
8280 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
8164 KB |
Output is correct |
2 |
Correct |
92 ms |
8176 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
50 ms |
8140 KB |
Output is correct |
5 |
Correct |
804 ms |
8164 KB |
Output is correct |
6 |
Correct |
187 ms |
8168 KB |
Output is correct |
7 |
Correct |
112 ms |
8172 KB |
Output is correct |
8 |
Correct |
893 ms |
8172 KB |
Output is correct |
9 |
Correct |
420 ms |
8152 KB |
Output is correct |
10 |
Execution timed out |
1094 ms |
8280 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |