This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("unroll-loops")
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |