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>
#define pb push_back
#define s second
#define f first
#define left (h<<1),l,(l + r)/2
#define right ((h<<1)|1),(l + r)/2 + 1,r
#define pii pair<int,int>
#define ll long long
using namespace std;
const int N = 500 + 5;
int a[N],n,sum;
bitset <250005> dp,ans;
void go(int l,int r){
if (l == r){
for (int x = 0; x <= 250000; x++){
int newsum = sum - a[l] + x;
if (!(newsum%2==0 && newsum/2 >= x && dp[newsum/2 - x]))
ans[x] = 0;
}
return;
}
int mid = (l + r)>>1;
//right child-shi gadavdivart
bitset <250005> olddp = dp;
for (int j = l; j <= mid; j++){
dp |= (dp << a[j]);
}
go(mid + 1,r);
//left child-shi gadavdivart
dp = olddp;
for (int j = mid + 1; j <= r; j++){
dp |= (dp << a[j]);
}
go(l,mid);
dp = olddp;
}
signed main (){
ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
cin>>n;
dp[0] = 1;
for (int i = 1; i <= n; i++){
cin >> a[i];
sum += a[i];
dp |= (dp << a[i]);
}
if (sum & 1 || !dp[sum/2]){
cout<<0;
exit(0);
}
for (int j = 0; j <= 250000; j++)
ans[j] = 1;
dp = 0;
dp[0] = 1;
go(1,n);
vector <int> res;
for (int j = 0; j <= 250000; j++)
if (ans[j]) res.pb(j);
cout<<(int)res.size()<<endl;
for (int x: res)
cout<<x<<" ";
}
# | 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... |