Submission #1127139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127139		brover29	Bootfall (IZhO17_bootfall)	C++20	100 / 100	229 ms	8740 KiB

bootfall

#include <bits/stdc++.h>
//qwerty47924692
using namespace std;
using ll = int;
const ll N=250000+3;
const ll mod=1e9+7;
const string br="617283";

ll n,tot,a[505],nxt[N],sz,s,cnt[N];
ll dp[N];

vector<ll>pos[N];
void solve(ll i,ll sum){
    ll prv=0;
    for(ll w=a[i];w<=tot;w++){
        dp[w]-=dp[w-a[i]];
    }

    for(ll x=1;x<=250000;x++){
        ll need=(sum+x)>>1;
//        if(x==1){
//            cout<<need<<' ';
//            return ;
//        }
        if(((sum+x+1)&1) && dp[need]){
           // cout<<x<<' '<<(dp[need/2])<<'\n';
            cnt[x]++;
            if(cnt[x]==n)sz++;
            continue;
        }


    }
    for(ll w=tot;w>=a[i];w--){
        dp[w]+=dp[w-a[i]];
    }

}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
        tot+=a[i];
    }
    dp[0]=1;
    for(ll i=1;i<=n;i++){
        for(ll w=tot;w>=a[i];w--){
            dp[w]+=dp[w-a[i]];

        }
    }


    if(!dp[tot/2]||tot&1){
        cout<<0;
        return 0;
    }

    for(ll i=1;i<=n;i++){
        solve(i,tot-a[i]);
//        return 0;
//        cout<<'\n';
    }
    cout<<sz<<'\n';
    for(ll x=1;x<=250000;x++){
        if(cnt[x]==n)cout<<x<<' ';
    }

}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 21 / 21
• Subtask 6: 35 / 35