Submission #346805

#TimeUsernameProblemLanguageResultExecution timeMemory
346805acmBootfall (IZhO17_bootfall)C++14
28 / 100
10 ms492 KiB
#include <bits/stdc++.h> #define speed \ ios_base::sync_with_stdio(0); \ cin.tie(0); \ cout.tie(0); #define precision \ cout.precision(30); \ cerr.precision(10); #define ll long long #define ld long double #define pll pair<ll, ll> #define pii pair<int, int> #define forn(n) for (int i = 1; i <= n; i++) #define forlr(l, r) for (int i = l; i != r; (l > r ? i-- : i++)) #define pb(x) push_back(x) #define sz(x) (int)x.size() #define mp(x, y) make_pair(x, y) #define all(x) x.begin(), x.end() #define pc(x) __builtin_popcount(x) #define pcll(x) __builtin_popcountll(x) #define F first #define S second using namespace std; int n, s, a[505], dp[50005]; bitset<50005> w; void add(int x) { s += x; for (int i = s - x; i >= 0; i--) dp[i + x] += dp[i]; } void del(int x) { for (int i = x; i <= s; i++) dp[i] -= dp[i - x]; s -= x; } int main() { speed; precision; // code cin >> n; dp[0] = 1; for (int i = 1; i <= n; i++) { cin >> a[i]; add(a[i]); } if (s % 2 || !dp[s / 2]) { cout << 0; return 0; } for (int i = 0; i <= 12500; i++) w[i] = 1; for (int i = 1; i <= n; i++) { del(a[i]); for (int j = 0; j <= 12500; j++) { if ((s + j) % 2 || !dp[(s + j) / 2]) w[j] = 0; } add(a[i]); } cout << w.count() << "\n"; for (int i = 1; i <= 12500; i++) if (w[i]) cout << i << " "; // endl #ifndef ONLINE_JUDGE cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; #endif 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...