Submission #1351341

#TimeUsernameProblemLanguageResultExecution timeMemory
1351341WarinchaiBootfall (IZhO17_bootfall)C++20
0 / 100
0 ms344 KiB
#include<bits/stdc++.h>
using namespace std;

int a[505];
int dp[2][500005];
int dp2[500005];
int st;
int X=1000;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    st=X/2*n;
    for(int i=0;i<=X*n+1;i++)dp[0][i]=dp[1][i]=0;
    dp[0][st]=1;
    for(int i=0;i<=X*n;i++)dp2[i]=1;
    int can=0;
    for(int i=1;i<=n+1;i++){
        int cur=0;
        for(int i=0;i<=X*n;i++)dp[0][i]=dp[1][i]=0;
        dp[0][st]=1;
        //cerr<<"i:"<<i<<"\n";
        for(int j=1;j<=n;j++){
            if(j==i)continue;
            cur^=1;
            for(int k=0;k<=X*n;k++)dp[cur][k]=0;
            //cerr<<"i:"<<i<<" "<<i%2<<"\n";
            for(int k=0;k<=X*n;k++){
                if(k-a[j]>=0)dp[cur][k]|=dp[cur^1][k-a[j]];
                if(k+a[j]<=X*n)dp[cur][k]|=dp[cur^1][k+a[j]];
            }
        }
        //cerr<<"i:"<<i<<"\n";
        //for(int j=0;j<=X*n;j++)cerr<<dp[cur][j]<<" ";
        //cerr<<"\n";
        if(i==n+1){
            for(int j=0;j<=X*n;j++){
                if(dp[cur][j])can=1;
            }
            break;
        }
        for(int j=0;j<=X*n;j++){
            dp2[j]&=dp[cur][j];
        }
    }
    if(can==0){
        cout<<0<<"\n";
        return 0;
    }
    vector<int>ans;
    for(int i=st;i<=X*n;i++)if(dp2[i]){
        ans.push_back(i-st);
    }
    cout<<ans.size()<<"\n";
    for(auto x:ans)cout<<x<<" ";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...