Submission #1127039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127039		brover29	Bootfall (IZhO17_bootfall)	C++20	28 / 100	1096 ms	23364 KiB

bootfall

#include <bits/stdc++.h>
//qwerty47924692
using namespace std;
using ll = int;
const ll N=2e5+29;
const string br="617283";

ll n,sum,a[505],nxt[N],sz,s;
bool dpr[505][N],dsu[505][N];
vector<ll>pos[N];
void solve(ll i,ll sum){
    ll prv=0;
    for(ll x=s;x<=72900;x=nxt[x]){
        ll need=(sum+x)>>1;
        if((sum+x)&1)goto doo;
        for(ll j:pos[i-1]){
            if(j>need)break;
            if(dsu[i+1][need-j]){
                prv=x;
               // cout<<x<<' ';
                goto fin;
            }
        }
        doo:;
        sz--;

        if(!prv){
            s=nxt[x];
        }else{
            nxt[prv]=nxt[x];
        }
        fin:;
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    sort(a+1,a+1+n);
    reverse(a+1,a+1+n);
    dpr[0][0]=1;
    dsu[n+1][0]=1;
    pos[0].push_back(0);
    for(ll i=1;i<=n;i++){
        for(ll w=0;w<=sum;w++){
            if(w>=a[i])dpr[i][w]|=dpr[i-1][w-a[i]];
            dpr[i][w]|=dpr[i-1][w];
            if(dpr[i][w])pos[i].push_back(w);
        }
    }for(ll i=n;i>=1;i--){
        for(ll w=sum;w>=0;w--){
            if(w>=a[i])dsu[i][w]|=dsu[i+1][w-a[i]];
            dsu[i][w]|=dsu[i+1][w];
        }
    }
    if(!dpr[n][sum/2]||sum&1){
        cout<<0;
        return 0;
    }
    s=1,sz=72900;
    for(ll i=1;i<=72900;i++){
        nxt[i]=i+1;
    }
    for(ll i=1;i<=n;i++){
        solve(i,sum-a[i]);
      //  return 0;
        //cout<<'\n';
    }
    cout<<sz<<'\n';
    for(ll x=s;x<=72900;x=nxt[x]){
        cout<<x<<' ';
    }

}

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