Submission #982164

#TimeUsernameProblemLanguageResultExecution timeMemory
982164LOLOLOBootfall (IZhO17_bootfall)C++17
0 / 100
1016 ms1368 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; #define f first #define s second #define pb push_back #define ep emplace #define eb emplace_back #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin()) #define mem(f,x) memset(f , x , sizeof(f)) #define sz(x) (int)(x).size() #define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b)) #define mxx *max_element #define mnn *min_element #define cntbit(x) __builtin_popcountll(x) #define len(x) (int)(x.length()) const int N = 500 + 30; const int M = (500 * 500 + 10) / 2; int f[M + 10], f2[M + 10], cnt[M + 10], mod = 1e8 + 3; int a[N]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); f[0] = 1; int sum = 0; int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; sum += a[i]; for (int j = M; j >= a[i]; j--) { f[j] = (f[j] + f[j - a[i]]) % mod; } } if (sum % 2 == 0) { if (f[sum / 2] == 0) { cout << 0 << '\n'; return 0; } } for (int i = 1; i <= n; i++) { int odd = (sum - a[i]) % 2; for (int j = odd; j <= M; j += 2) { int all = sum - a[i] + j; for (int j = 0; j <= M; j++) { if (j >= a[i]) { f2[j] = (f[j] - f2[j - a[i]]); while (f2[j] < 0) f2[j] += mod; } else { f2[j] = f[j]; } } if (all % 2 == 0) { int h = all / 2; if (f2[h] || (h >= j && f2[h - j])) { cnt[j]++; } } } } vector <int> save; for (int i = 1; i <= M; i++) if (cnt[i] == n) save.pb(i); cout << sz(save) << '\n'; for (auto x : save) cout << x << " "; 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...