oj.uz

Submission #1089413

# Submission time Handle Problem Language Result Execution time Memory
1089413 2024-09-16T12:42:32 Z vjudge1 Kpart (eJOI21_kpart) C++17
100 / 100
 1438 ms 968 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;
    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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 856 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 604 KB Output is correct
2 Correct 145 ms 856 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 856 KB Output is correct
2 Correct 521 ms 856 KB Output is correct
3 Correct 523 ms 884 KB Output is correct
4 Correct 735 ms 920 KB Output is correct
5 Correct 1093 ms 948 KB Output is correct
6 Correct 1438 ms 968 KB Output is correct
7 Correct 1397 ms 860 KB Output is correct