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;
#define int long long
const int mod = 1e9 + 7;
const int maxn = 1e3 + 10;
const int maxs=1e5+10;
const int logn=20;
int n;
int dp[maxs];
int ans[maxn];
signed main()
{
///freopen("sirbun.in","r",stdin);
///freopen("sirbun.out","w",stdout);
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
cin>>n;
memset(dp,0,sizeof dp);
for(int i=0;i<=n;i++)
{
ans[i]=1;
}
int a[n+1];
int S=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
S+=a[i];
for(int j=S;j>=a[i];j--)
{
dp[j]=max(dp[j],dp[j-a[i]]);
}
dp[0]=dp[a[i]]=i;
int sum=0;
for(int j=i;j>=1;j--)
{
sum+=a[j];
if(sum%2==1 || dp[sum/2]<j)
{
ans[i-j+1]=0;
}
}
}
int kol=0;
for(int i=1;i<=n;i++)
{
kol+=ans[i];
}
cout<<kol<<" ";
for(int i=1;i<=n;i++)
{
if(ans[i])
cout<<i<<" ";
}
cout<<endl;
}
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... |