This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define sz(s) (int)s.size()
#define ll long long
#define ff first
#define ss second
const int N = 2e3 + 5;
const ll M = 1e9+7;
int n, a[N];
int main(){
cin >> n;
int mx = 0;
ll s = 0;
for(int i = 1; i <= n; i++){
cin >> a[i];
s += a[i];
mx = max(a[i],mx);
}
vector <vector<int>> dp(n+1, vector <int> (mx*n+1,0));
vector <int> v;
for(int i = 1; i <= n; i++){
v.clear();
for(int j = 1; j <= n; j++){
if(j == i) continue;
v.push_back(a[j]);
}
dp[i][0] = 1;
for(int j = 0; j < sz(v); j++){
for(int k = min((ll)500,s)-v[j]; k >= 0; k--){
if(dp[i][k] == 1) dp[i][k+v[j]] = 1;
}
}
}
if(!dp[1][s/2] or s % 2 == 1){
cout << 0;
return 0;
}
v.clear();
for(int i = (a[1] % 2 == 0 ? 2 : 1); i <= n*mx; i += 2){
bool tr = 0;
for(int j = 1; j <= n; j++){
ll x = s-a[j]+i;
if(!dp[j][x/2] or x % 2 == 1){
tr = 1;
break;
}
}
if(tr == 0) v.push_back(i);
}
cout << sz(v) << '\n';
for(int i : v){
cout << i << ' ';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |