Submission #913998

#TimeUsernameProblemLanguageResultExecution timeMemory
913998MisterReaperKpart (eJOI21_kpart)C++17
100 / 100
861 ms1720 KiB
#include <bits/stdc++.h> using i64 = long long; #define ONLINE_JUDGE void solve() { int n; std::cin >> n; std::vector<int> a(n + 1); for(int i = 1; i <= n; i++) { std::cin >> a[i]; } int sum = 0; std::vector<int> dp(1), ans(n + 1, true); for(int i = 1; i <= n; i++) { sum += a[i]; dp.resize(sum + 1, -1); for(int j = sum; j >= a[i]; j--) { dp[j] = std::max(dp[j], dp[j - a[i]]); } dp[a[i]] = i; /* for(int i = 0; i <= sum; i++) { std::cerr << dp[i] << " \n"[i == sum]; } */ int ssum = 0; for(int j = i; j >= 1; j--) { ssum += a[j]; ans[i - j + 1] &= (ssum % 2 == 0 && dp[ssum / 2] >= j); } } std::vector<int> pr; for(int i = 1; i <= n; i++) { if(ans[i]) { pr.emplace_back(i); } } std::cout << int(pr.size()) << " "; for(int &i : pr) { std::cout << i << " "; } std::cout << "\n"; return; } signed main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL); int t = 1; std::cin >> t; for(int i = 1; i <= t; i++) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...