Submission #697599

#TimeUsernameProblemLanguageResultExecution timeMemory
697599Ooops_sorryKpart (eJOI21_kpart)C++14
100 / 100
763 ms812 KiB
#include<bits/stdc++.h> using namespace std; #define ull unsigned long long #define pb push_back #define ld long double #define ll long long #define all(a) a.begin(), a.end() mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count()); const int N = 1010, M = 1e5 + 10; int a[N], pr[N], mx[M]; signed main() { #ifdef LOCAL freopen("input.txt", "r", stdin); #endif // LOCAL ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) { int n; cin >> n; int sum = 0; for (int i = 1; i <= n; i++) { cin >> a[i]; pr[i] = pr[i - 1] + a[i]; sum += a[i]; } for (int i = 0; i <= sum; i++) { mx[i] = -1; } vector<int> good(n + 1, 1); for (int i = 1; i <= n; i++) { for (int j = sum / 2 - a[i]; j >= 0; j--) { mx[j + a[i]] = max(mx[j + a[i]], mx[j]); } mx[a[i]] = i; for (int j = i; j >= 1; j--) { if ((pr[i] - pr[j - 1]) & 1) { good[i - j + 1] = 0; } else { good[i - j + 1] &= j <= mx[(pr[i] - pr[j - 1]) / 2]; } } } vector<int> ans; for (int i = 1; i <= n; i++) { if (good[i]) { ans.pb(i); } } cout << ans.size() << ' '; for (auto to : ans) cout << to << ' '; cout << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...