제출 #91245

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
91245		Abelyan	Bootfall (IZhO17_bootfall)	C++17	100 / 100	392 ms	3504 KiB

bootfall

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pr;

#define fr first
#define sc second
#define FOR(i, a) for (int i = 0; i < (a); i++)
#define F0R(i, a, b) for (int i = (a); i <= (b); i++)
#define FORd(i,a) for (int i = (a)-1; i >= 0; i--)
#define F0Rd(i,a,b) for (int i = (b); i >= (a); i--)
#define trav(a, x) for (auto& a : x)

const int N=5000006;

int sum;
int a[N];
ll dp[N];
bool cant[N];
void add(ll k){
    sum+=k;
    for (int i=sum;i>=k;i--){
        dp[i]+=dp[i-k];
    }
}

void rem(ll k){
    for (int i=k;i<=sum;i++){
        dp[i]-=dp[i-k];
    }
    sum-=k;
}

int main(){
    ios_base::sync_with_stdio(false);
    #ifndef EVAL
    freopen("input.txt","r",stdin);
    #endif
    int n;
    cin>>n;
    dp[0]=1;
    FOR(i,n){
        cin>>a[i];
        add(a[i]);
    }

    if (sum%2==1 || dp[sum/2]==0){
        //cout<<dp[sum/2]<<endl;
        cout<<0<<endl;
        return 0;
    }
    int hn=sum;
    FOR(i,n){
        rem(a[i]);
        FOR(j,hn+1){
            //cout<<a[i]<<" "<<j<<" "<<dp[j]<<endl;
            if ((sum+j)%2==1 || dp[(sum+j)/2]==0){
                cant[j]=true;
            }
        }
        add(a[i]);
    }
    int ans=0;
    FOR(j,hn+1)
        if (!cant[j])
            ans++;
    cout<<ans<<endl;
    FOR(j,hn+1)
        if (!cant[j])
            cout<<j<<" ";
    return 0;
}

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