Submission #636229

#TimeUsernameProblemLanguageResultExecution timeMemory
636229Valaki2Kpart (eJOI21_kpart)C++14
0 / 100
435 ms768 KiB
#include <bits/stdc++.h> using namespace std; #define sum(l, r) (pref[(r)] - pref[(l) - 1]) const int maxn = 1e3; const int maxv = 1e5; const int inf = 1e9; int n; int v[maxn + 1]; int pref[maxn + 1]; int dp[maxv + 1]; bool ans[maxn + 1]; int ans_cnt; void solve() { cin >> n; for(int i = 1; i <= n; i++) { ans[i] = true; cin >> v[i]; pref[i] = pref[i - 1] + v[i]; } dp[0] = inf; int s = -1; for(int i = 1; i <= n; i++) { for(int j = maxv; j >= v[i]; j--) { dp[j] = max(dp[j], min(dp[j - v[i]], i)); } for(int k = 1; k <= i; k++) { s = sum(k, i); if((s % 2 == 1) || (dp[s / 2] < k)) { ans[i - k + 1] = false; } } } ans_cnt = 0; for(int i = 1; i <= n; i++) { if(ans[i]) { ans_cnt++; } } cout << ans_cnt << " "; for(int i = 1; i <= n; i++) { if(ans[i]) { cout << i << " "; } } cout << "\n"; } int main() { 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...