Submission #1089413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089413		vjudge1	Kpart (eJOI21_kpart)	C++17	100 / 100	1438 ms	968 KiB

Main

#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';
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70