Submission #964868

#TimeUsernameProblemLanguageResultExecution timeMemory
964868zxciganKpart (eJOI21_kpart)C++17
100 / 100
1587 ms195848 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; const int N = 1e6 + 1; const int mod = 1e9 + 7; template <typename T> bool umx(T& a, T b) { return (a < b ? a = b, 1 : 0); } template <typename T> bool umn(T& a, T b) { return (a > b ? a = b, 1 : 0); } int dp[1001][(int)5e4 + 2]; void solve () { int n; cin >> n; vector<int> a (n + 1); vector<int> pref (n + 1); for (int i = 1; i <= n; ++i) cin >> a[i], pref[i] = pref[i - 1] + a[i]; for (int i = 1; i <= n; ++i) { for (int j = 0; j <= 5e4; ++j) dp[i][j] = dp[i - 1][j]; dp[i][a[i]] = i; for (int j = 1; j <= 5e4; ++j) { if (j + a[i] > 5e4) break; umx (dp[i][j + a[i]], dp[i - 1][j]); } } vector<int> ans; for (int k = 1; k <= n; ++k) { bool bad = false; for (int l = 1; l <= n; ++l) { int r = l + k - 1; if (r > n) break; int s = pref[r] - pref[l - 1]; if (s % 2) { bad = 1; break; } if (dp[r][s >> 1] < l) { bad = 1; break; } } if (!bad) ans.push_back(k); } cout << (int)ans.size() << ' '; for (auto it : ans) cout << it << ' '; cout << "\n"; } signed main() { #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #else // freopen ("input.txt", "r", stdin); // freopen ("output.txt", "w", stdout); #endif ios_base::sync_with_stdio(false); cin.tie(nullptr); int T = 1; cin >> T; while (T--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...