Submission #523844

#TimeUsernameProblemLanguageResultExecution timeMemory
523844Bill_00Bootfall (IZhO17_bootfall)C++14
44 / 100
1014 ms844 KiB
#include<bits/stdc++.h> #pragma GCC target("popcnt") #define N 1000005 typedef long long ll; using namespace std; int a[N]; int n; int sum; bitset<250001> BS, ans, g; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); for(int i = 1; i <= 250000; i++){ ans[i] = 1; } int n; cin >> n; BS[0] = 1; for(int i = 1; i <= n; i++){ cin >> a[i]; sum += a[i]; BS = BS | (BS << a[i]); } if(sum % 2 == 0){ int k = sum >> 1; if(BS[k] == 0){ cout << 0; return 0; } } else{ cout << 0; return 0; } for(int i = 1; i <= n; i++){ BS.reset(); g.reset(); sum = 0; BS[0] = 1; for(int j = 1; j <= n; j++){ if(i != j){ BS = BS | (BS << a[j]); sum += a[j]; } } for(int j = 0; j <= sum; j++){ if(BS[j] == 1){ g[abs(sum - 2 * j)] = 1; } } ans &= g; } vector<int> anss; for(int i = 1; i <= 250000; i++){ if(ans[i] == 1){ anss.push_back(i); } } cout << anss.size() << '\n'; for(int value : anss) cout << value << ' '; }
#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...