Submission #1127028

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127028		brover29	Bootfall (IZhO17_bootfall)	C++20	13 / 100	1090 ms	3084 KiB

bootfall

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

ll n,cnt[N],sum,a[N];
bool dpr[505][N],dsu[505][N];
void solve(ll i,ll sum){
    for(ll x=1;x<=10000;x++){
        ll need=(sum+x)>>1;
        if((sum+x)&1)continue;
        for(ll j=0;j<=need;j++){
            if(dpr[i-1][j]&&dsu[i+1][need-j]){
                cnt[x]++;
              //  cout<<x<<' ';
                break;
            }
        }
    }
}
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];
    }
    dpr[0][0]=1;
    dsu[n+1][0]=1;
    for(ll i=1;i<=n;i++){
        for(ll w=sum;w>=0;w--){
            if(w>=a[i])dpr[i][w]|=dpr[i-1][w-a[i]];
            dpr[i][w]|=dpr[i-1][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;
    }
    for(ll i=1;i<=n;i++){
        solve(i,sum-a[i]);
        //cout<<'\n';
    }
    vector<ll>v;
    for(ll i=1;i<=10000;i++){

        if(cnt[i]==n){
            v.push_back(i);
        }
    }
    cout<<v.size()<<'\n';
    for(ll i:v){
        cout<<i<<' ';
    }

}

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