Submission #1352154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1352154		Newtonabc	Bootfall (IZhO17_bootfall)	C++20	28 / 100	27 ms	1716 KiB

bootfall

#include<bits/stdc++.h>
using namespace std;
const int N=25100;
bitset<N> dp[510],sf[510];
int a[600];
int main(){
    int n; cin>>n;
    int sum=0;
    dp[0][0]=1;
    for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
    for(int i=1;i<=n;i++){
        dp[i]=dp[i-1]|(dp[i-1]<<a[i]);
    }
    if(sum%2==1 || dp[n][sum/2]==0){
        cout<<0;
        return 0;
    }
    for(int i=1;i<=n;i++){
        vector<int> v;
        for(int j=1;j<=n;j++) if(j!=i) v.push_back(a[j]);
        dp[0]=0;
        dp[0][0]=1;
        for(int j=1;j<n;j++){
            dp[j]=dp[j-1]|(dp[j-1]<<v[j-1]);
        }
        sf[i]=dp[n-1];
    }
    vector<int> ans;
    for(int i=1;i<=sum;i++){
        bool ok=1;
        int ts=sum+i;
        for(int j=1;j<=n;j++){
            int tar=ts-a[j];
            if(tar%2==1 || sf[j][tar/2]==0){
                ok=false;
                break;
            }
        }
        if(ok) ans.push_back(i);
    }
    cout<<ans.size() <<"\n";
    for(int i=0;i<ans.size();i++) cout<<ans[i] <<" \n"[i==(int)ans.size()-1];
}

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