Submission #1088843

#TimeUsernameProblemLanguageResultExecution timeMemory
1088843TrinhKhanhDungBootfall (IZhO17_bootfall)C++14
100 / 100
243 ms3400 KiB
#include <bits/stdc++.h> #define ll long long #define fi first #define se second #define sz(x) (int)x.size() #define ALL(v) v.begin(),v.end() #define MASK(k) (1LL << (k)) #define BIT(x, i) (((x) >> (i)) & 1) #define oo (ll)1e18 #define INF (ll)1e9 #define MOD (ll)(1e9 + 7) using namespace std; template<class T1, class T2> bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;} template<class T1, class T2> bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;} template<class T1, class T2> void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;} template<class T1, class T2> void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;} template<class T> void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());} const int MAX = 503; int N; int a[MAX], f[MAX * MAX]; void solve(){ cin >> N; int S = 0; for(int i = 1; i <= N; i++){ cin >> a[i]; S += a[i]; } f[0] = 1; for(int i = 1; i <= N; i++){ for(int j = S; j >= a[i]; j--){ f[j] += f[j - a[i]]; } } if(S % 2 || !f[S / 2]){ cout << 0 << '\n'; return; } vector<int> ans; for(int i = 1; i <= S; i++) ans.push_back(i); for(int i = 1; i <= N; i++){ for(int j = a[i]; j <= S; j++) f[j] -= f[j - a[i]]; vector<int> tmp; tmp.reserve(sz(ans)); for(int x: ans){ int tS = S - a[i] + x; if(tS % 2 == 0 && f[tS / 2]){ tmp.push_back(x); } } ans = tmp; for(int j = S; j >= a[i]; j--) f[j] += f[j - a[i]]; } cout << sz(ans) << '\n'; for(int x: ans) cout << x << ' '; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); // freopen("order.inp","r",stdin); // freopen("order.out","w",stdout); solve(); return 0; }
#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...