제출 #1089410

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1089410		vjudge1	Kpart (eJOI21_kpart)	C++17	0 / 100	296 ms	860 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;

    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))){
                continue;
            }
            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: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 70