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>
#define int long long
#define MOD 1000000007
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int32_t main(){
fast;
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<int>arr(n);
int s=0;
for(int i=0;i<n;i++){
cin>>arr[i];
s+=arr[i];
}
vector<int>pre(n);
for(int i=0;i<n;i++){
pre[i]=(i==0?0:pre[i-1])+arr[i];
}
auto get=[&](int l,int r)->int{
return pre[r]-(l==0?0:pre[l-1]);
};
vector<int>ans(n,1),dp(s+1,-1);
for(int i=0;i<n;i++){
dp[0]=i;
for(int j=s;j>=arr[i];j--){
dp[j]=max(dp[j],dp[j-arr[i]]);
}
for(int j=i;j>=0;j--){
if(get(j,i)%2!=0 || dp[get(j,i)/2]<j){
ans[i-j]=0;
}
}
}
cout<<count(all(ans),1LL)<<" ";
for(int i=0;i<n;i++){
if(ans[i]){
cout<<i+1<<" ";
}
}
cout<<endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |