제출 #990181

#제출 시각아이디문제언어결과실행 시간메모리
990181tch1cherinBootfall (IZhO17_bootfall)C++17
28 / 100
80 ms1168 KiB
#include <bits/stdc++.h> using namespace std; int main() { cin.tie(nullptr)->sync_with_stdio(false); int N; cin >> N; vector<int> a(N); for (int &value : a) { cin >> value; } int S = accumulate(a.begin(), a.end(), 0); for (int i = 0; i < N; i++) { if (a[i] % 2 != a[0] % 2 || S % 2) { cout << "0\n"; exit(0); } } vector<uint64_t> rnd(N); mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); for (int i = 0; i < N; i++) { rnd[i] = rng(); } vector<uint64_t> dp(S + 1); dp[0] = 1; for (int i = 0; i < N; i++) { for (int j = S - a[i]; j >= 0; j--) { dp[j + a[i]] += dp[j]; } } if (dp[S / 2] == 0) { cout << "0\n"; exit(0); } vector<bool> good(S + 1, true); for (int i = 0; i < N; i++) { for (int j = 0; j + a[i] <= S; j++) { dp[j + a[i]] -= dp[j]; } vector<bool> new_good(S + 1); for (int j = 0; j <= S; j++) { if (dp[j] > 0) { new_good[abs(2 * j - (S - a[i]))] = true; } } for (int j = 0; j <= S; j++) { good[j] = good[j] && new_good[j]; } for (int j = S - a[i]; j >= 0; j--) { dp[j + a[i]] += dp[j] * rnd[i]; } } vector<int> answer; for (int i = 1; i <= S; i++) { if (good[i]) { answer.push_back(i); } } int k = (int)answer.size(); cout << k << "\n"; for (int i = 0; i < k; i++) { cout << answer[i] << " \n"[i + 1 == k]; } }
#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...