제출 #1089413

#제출 시각아이디문제언어결과실행 시간메모리
1089413vjudge1Kpart (eJOI21_kpart)C++17
100 / 100
1438 ms968 KiB
#include <bits/stdc++.h>
//qwerty47924692
using namespace std;
using ll = int;
const ll N=1e5+29;
ll n,t,a[N],dp[N],pref[N];

void solve(){
    cin>>n;
    for(ll i=0;i<N;i++)dp[i]=0;
    set<ll>v;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
        pref[i]=pref[i-1]+a[i];
        if(i>1)v.insert(i);
    }
    for(ll i=1;i<=n;i++){
        for(ll w=N-1;w>a[i];w--){
                dp[w]=max(dp[w],dp[w-a[i]]);

        }
        dp[a[i]]=i;
        for(ll k=2;k<=i;k++){
            ll sum=pref[i]-pref[i-k];
            if(dp[sum/2]<i-k+1||((sum&1))){

                v.erase(k);
            }
        }
    }

   // cout<<dp[1][4][8]<<' ';
    cout<<v.size();

    for(ll i:v){
        cout<<' '<<i;
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll t;

    cin>>t;
    while(t--){
        solve();
        cout<<'\n';
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...