Submission #1351384

#TimeUsernameProblemLanguageResultExecution timeMemory
1351384WarinchaiBootfall (IZhO17_bootfall)C++20
100 / 100
268 ms7692 KiB
#include<bits/stdc++.h>
#define int long long
using namespace std;

int a[505];
int dp[500005];
int val[500005];
int can[500005];
int st;
int X=1000;

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    int sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    dp[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=sum;j>=0;j--){
            if(j-a[i]>=0)dp[j]+=dp[j-a[i]];
        }
    }
    if(sum%2==1||dp[sum/2]==0){
        cout<<"0\n";
        return 0;
    }
    for(int i=0;i<=sum;i++)can[i]=0;
    //for(int i=0;i<=sum;i++)cerr<<dp[i]<<" ";
    //cerr<<"\n";
    for(int i=1;i<=n;i++){
        for(int j=0;j<=sum;j++)val[j]=dp[j];
        for(int j=0;j<=sum;j++){
            if(j-a[i]>=0)dp[j]-=dp[j-a[i]];
        }
        //cerr<<"i:"<<i<<"\n";
        for(int j=0;j<=sum;j++){
            if(dp[j]&&(sum-a[i]-2*j>=0)){
                can[sum-a[i]-2*j]++;
                //cerr<<"can:"<<sum-a[i]-2*j<<"\n";
            }
        }
        for(int j=sum;j>=0;j--){
            if(j-a[i]>=0)dp[j]+=dp[j-a[i]];
        }
    }
    vector<int>ans;
    for(int i=0;i<=sum;i++)if(can[i]==n)ans.push_back(i);
    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...