Submission #912589

#TimeUsernameProblemLanguageResultExecution timeMemory
912589androKpart (eJOI21_kpart)C++14
0 / 100
2049 ms1056 KiB
#include <bits/stdc++.h> #define int long long #define double long double using namespace std; const int N = 1e6; bitset<N> dp; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while(t-- ) { int n; cin >> n; vector<int> a(n + 1); for(int i = 1; i <= n; i++) { cin >> a[i]; } vector<int> ans; vector<int> pref(n + 1); for(int i = 1; i <= n; i++) { pref[i] = pref[i - 1] + a[i]; } for(int k = 1; k <= n; k++) { dp[0] = 1; for(int i = 1; i <= k; i++) { dp |= (dp << a[i]); } if(pref[k] % 2) { continue; } if(! dp[(pref[k]) / 2]) { continue; } int ok = 1; for(int i = k + 1; i <= n; i++) { dp &= (dp >> a[i - k]); dp[0] = 1; dp |= (dp << a[i]); if((pref[i] - pref[i - k]) % 2) { ok = 0; break; } if(! dp[(pref[i] - pref[i - k]) / 2]) { ok = 0; break; } } dp.reset(); if(ok) { ans.push_back(k); } } cout << ans.size() << " "; for(auto it : ans) { cout << it << " "; } cout << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...