Submission #38458

#TimeUsernameProblemLanguageResultExecution timeMemory
38458MrPlanyBootfall (IZhO17_bootfall)C++14
13 / 100
83 ms5112 KiB
//Bismillahi-rahmani-rahim #include <bits/stdc++.h> #include <algorithm> using namespace std; typedef long long ll; typedef map <int, int> mii; typedef pair <int, int> pii; typedef pair <ll, ll> pll; const int inf=1e9; #define azdar priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> #define Lebap ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0); #define mp make_pair #define pb push_back #define pf push_front #define pk pop_back #define ff first #define ss second #define all(x) x.begin(), x.end() //#include <conio.h> #include <climits> const int N = 250000; int n, a[509], dp[N+609], dp1[N+609], cnt[N+609]; int main(){ Lebap; cin>>n; int sum=0; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) sum += a[i]; dp[0]=1; for(int i=1;i<=n;i++){ for(int j=N;j>=0;j--){ dp[j+a[i]]+=dp[j]; } } if(sum%2!=0 || dp[sum/2]==0) return cout << 0 , 0; for(int i=1;i<=n;i++){ memset( dp1, 0, sizeof(dp1) ); for(int j=0;j<=N;j++){ dp1[j]+=dp[j]; dp1[j+a[i]]-=dp1[j]; } for(int j=0;j<=N;j++){ if(sum-a[i]-j>=0 && (sum-a[i]+j)%2==0 && dp1[ (sum-a[i]-j)/2 ]!=0) cnt[j]++; } } vector <int> ans; ans.clear(); for(int i=1;i<=N;i++) if( cnt[i] == n ) ans.pb(i); cout << ans.size() << endl; for(auto i : ans) cout << i << " "; }
#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...