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], vis[N*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 <int> dp(s+1,0), dp1(s+1,0), v, dp2(s+1,0);
dp[0] = dp1[0] = 1;
for(int i = 1; i <= n; i++){
for(int k = s-a[i]; k >= 0; k--){
if(dp[k] == 1) dp[k+a[i]] = 1, dp1[k+a[i]] += dp1[k];
}
}
if(!dp[s/2] or s % 2 == 1){
cout << 0;
return 0;
}
v.clear();
for(int i = 1; i <= n; i++){
for(int j = a[i]; j <= s; j++){
dp1[j] -= dp1[j - a[i]];
}
for(int j = 1; j <= s; j++){
ll x = s - a[i] + j;
vis[j] += ((dp1[x/2]) and (x % 2 == 0));
}
for(int j = s; j >= a[i]; j--){
dp1[j] += dp1[j - a[i]];
}
}
for(int i = 1; i <= s; i++){
if(vis[i] == n){
v.push_back(i);
}
}
cout << sz(v) << '\n';
for(auto 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... |