Submission #886977

#TimeUsernameProblemLanguageResultExecution timeMemory
886977NintsiChkhaidzeBootfall (IZhO17_bootfall)C++17
100 / 100
219 ms2640 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...