# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1115438 | 2024-11-20T13:07:27 Z | vjudge1 | Bootfall (IZhO17_bootfall) | C++17 | 0 ms | 0 KB |
#pragma optimize ("g",on) #pragma GCC optimize("inline") #pragma GCC optimize ("Ofast") #pragma GCC optimize ("unroll-loops") #pragma GCC optimize ("03") #include <bits/stdc++.h> #define ios ios_base::sync_with_stdio(0); cin.tie(0); #define pb push_back using namespace std; typedef int ll; const int mxN = 5e2; const int mxSm = mxN * mxN; int dp[mxSm + 1]; vector<int> ans; int a[mxN]; int s; void solve() { int N; cin >> N; for (int i = 1; i <= mxSm; i ++) { ans.pb(i); } dp[0] = 1; for (int i = 0; i < N; i ++) { cin >> a[i]; for (int j = mxSm; j >= a[i]; j --) { dp[j] += dp[j - a[i]]; } s += a[i]; } if (s % 2 || dp[s / 2] == 0) { cout << "0\n"; return; } for (int i = 0; i < N; i ++) { s -= a[i]; for (int j = a[i]; j <= mxSm; j ++) { dp[j] -= dp[j - a[i]]; } int j = 0; while (j<(int)ans.size()){ if (s < ans[j] || (s - ans[j]) % 2 || !dp[(s - ans[j]) / 2]) { if (j < (int)ans.size()) { swap(ans[j], ans[(int)ans.size()-1]); } ans.pop_back(); } else { j ++; } } s += a[i]; for (int j = mxSm; j >= a[i]; j --) { dp[j] += dp[j - a[i]]; } } sort(begin(ans),end(ans)); cout << ans.size() << "\n"; for (int i : ans) { cout << i << ' '; } } signed main() { ios(); solve(); }