Submission #636236

#TimeUsernameProblemLanguageResultExecution timeMemory
636236Valaki2Kpart (eJOI21_kpart)C++14
30 / 100
2071 ms644 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize ("unroll-loops","Ofast") #define sum(l, r) (pref[(r)] - pref[(l) - 1]) const int maxn = 1e3; const int maxv = 1e5; int n; int v[maxn + 1]; int pref[maxn + 1]; short dp[maxv + 1]; bool ans[maxn + 1]; int ans_cnt; void solve() { cin >> n; for(short i = 1; i <= n; i++) { ans[i] = true; cin >> v[i]; pref[i] = pref[i - 1] + v[i]; } dp[0] = maxn + 1; for(int j = 1; j <= maxv; j++) { dp[j] = 0; } int s = -1; for(short 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(short k = 1; k <= i; k++) { s = sum(k, i); if((s & 1) || (dp[s / 2] < k)) { ans[i - k + 1] = false; } } } ans_cnt = 0; for(short i = 1; i <= n; i++) { if(ans[i]) { ans_cnt++; } } cout << ans_cnt << " "; for(short 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...