Submission #1306263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306263		h1drogen	Kpart (eJOI21_kpart)	C++20	100 / 100	1068 ms	1972 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
const int mod=1e9+7;
int modi(int a,int b){
    return (a*b)%mod;
}
void solve(){
    int n;
    cin>>n;
    vector<int>v(n+1);
    for(int i=1;i<=n;i++){
        cin>>v[i];
    }
    vector<int>dp(100005,0);
    vector<int>cnt(n+1,0);
    dp[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=100000-v[i];j>0;j--){
            if(dp[j]){
                dp[j+v[i]]=max(dp[j+v[i]],dp[j]);
            }
        }
        dp[v[i]]=i;
        int sum=0;
        for(int j=i;j>0;j--){
            sum+=v[j];
            if(sum%2){
                cnt[i-j+1]=1;
            }
            if(dp[sum/2]<j){
                cnt[i-j+1]=1;
            }
        }
    }
    vector<int>ans;
    for(int i=1;i<=n;i++){
        if(!cnt[i])
            ans.pb(i);
    }
    cout<<ans.size()<<" ";
    for(auto k:ans){
        cout<<k<<" ";
    }
    cout<<"\n";
}
signed main() {
    int t=1;
    cin >>t;
    while(t--){
        solve();
    }
    return 0;
}

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