Submission #1127055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127055		brover29	Bootfall (IZhO17_bootfall)	C++20	65 / 100	1094 ms	7692 KiB

bootfall

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

ll n,sum,a[505],nxt[N],sz,s;
bool dpr[505][N],dsu[505][N];
bitset<N>dp;
vector<ll>pos[N];
void solve(ll i,ll sum){
    ll prv=0;
    dp.reset();
    dp[0]=1;
    for (ll j = 1; j <= n; j++) {
        if (i == j) continue;
        dp |= (dp << a[j]);
    }
    for(ll x=s;x<=250000;x=nxt[x]){
        ll need=(sum+x)>>1;
        if((sum+x)&1)goto doo;

        if(dp[need]){
            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);
    dp.reset();
    dp[0]=1;
    for (ll j = 1; j <= n; j++) {
        dp |= (dp << a[j]);
    }
    if(!dp[sum/2]||sum&1){
        cout<<0;
        return 0;
    }
    s=1,sz=250000;
    for(ll i=1;i<=250000;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<=250000;x=nxt[x]){
        cout<<x<<' ';
    }

}

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