Submission #954083

#TimeUsernameProblemLanguageResultExecution timeMemory
954083nguyennhBootfall (IZhO17_bootfall)C++14
13 / 100
1024 ms816 KiB
#include<bits/stdc++.h> #define el '\n' using namespace std ; const int MN = 1e5 + 5; int n; namespace sub_trau{ int64_t dp[MN]; // check whether existing a way to divide array into 2 parts with sum = x; void solve(){ vector<int> a(n + 5); for ( int i = 1 ; i <= n ; i++ ) cin >> a[i]; if (n & 1){ cout << 0; return; } bool odd = false , even = false; for ( int i = 1 ; i <= n ; i++ ){ odd |= (a[i] & 1); even |= (a[i] % 2 == 0); } if (odd && even){ cout << 0; return; } bitset<MN> bit; bit[0] = 1; for ( int i = 1 ; i <= n ; i++ ) bit |= (bit << a[i]); int sum = accumulate(a.begin() + 1 , a.begin() + n + 1 , 0); int mn = *min_element(a.begin() + 1 , a.begin() + n + 1); if (!bit[sum / 2]){ cout << 0; return; } dp[0] = 1; for ( int i = 1 ; i <= n ; i++ ){ for ( int j = sum ; j >= a[i] ; j-- ) dp[j] += dp[j - a[i]]; } vector<int> ans , candidates; for ( int i = 1 ; i <= n ; i++ ) candidates.push_back(a[i]); for ( int val = odd ? 1 : 2 ; val <= sum - mn ; val += 2 ){ int all = sum + val; candidates.push_back(val); for ( int j = all ; j >= val ; j-- ) dp[j] += dp[j - val]; bool check = true; for ( int turn = 0 ; turn < n ; turn++ ){ if (!check) break; int need = all - candidates[turn]; if (need & 1){ check = false; break; } for ( int j = candidates[turn] ; j <= need / 2 ; j++ ){ dp[j] -= dp[j - candidates[turn]]; } if (!dp[need / 2]){ check = false; } for ( int j = need / 2 ; j >= candidates[turn] ; j-- ) dp[j] += dp[j - candidates[turn]]; } if (check) ans.push_back(val); candidates.pop_back(); for ( int j = val ; j <= all ; j++ ) dp[j] -= dp[j - val]; } cout << ans.size() << el; for ( auto x : ans ) cout << x << " "; } } int32_t main (){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; sub_trau::solve(); }
#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...