oj.uz

Submission #1089410

# Submission time Handle Problem Language Result Execution time Memory
1089410 2024-09-16T12:40:08 Z vjudge1 Kpart (eJOI21_kpart) C++17
0 / 100
 296 ms 860 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 296 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -