#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;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
348 KB |
Output is correct |
2 |
Correct |
24 ms |
576 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
95 ms |
660 KB |
Output is correct |
2 |
Correct |
271 ms |
768 KB |
Output is correct |
3 |
Correct |
302 ms |
768 KB |
Output is correct |
4 |
Correct |
559 ms |
920 KB |
Output is correct |
5 |
Correct |
1273 ms |
1112 KB |
Output is correct |
6 |
Correct |
1841 ms |
1308 KB |
Output is correct |
7 |
Correct |
1674 ms |
1260 KB |
Output is correct |