Submission #1112895

#TimeUsernameProblemLanguageResultExecution timeMemory
1112895adiyerBootfall (IZhO17_bootfall)C++17
65 / 100
1016 ms1424 KiB
#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 N = 5e2 + 11; const int MAX = 1e6; short int n; int s; short int a[N]; bool ok[500 * 500 + 3]; bitset < 500 * 500 + 3 > dp; void sol(){ cin >> n, dp[0] = 1; for(ll i = 1; i <= 500 * 500; i++) ok[i] = 1; for(ll i = 1; i <= n; i++) cin >> a[i], dp |= (dp << a[i]), s += a[i]; if(s % 2 || dp[s / 2] == 0){ cout << "0\n"; return; } for(short int i = 1; i <= n; i++){ dp &= 0; dp[0] = 1, s = 0; for(short int j = 1; j <= n; j++) if(i != j) dp |= (dp << a[j]), s += a[j]; for(int j = 1; j <= 500 * 500; j++){ if(s < j || (s - j) % 2) ok[j] = 0; else ok[j] &= dp[(s - j) / 2]; } } vector < int > ans; for(int i = 1; i <= 500 * 500; i++){ if(ok[i]){ ans.pb(i); } } cout << ans.size() << '\n'; for(int x : ans) cout << x << ' '; } signed main(){ ios sol(); // slow(); // stress(); }
#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...