Submission #334665

#	Time	Username	Problem	Language	Result	Execution time	Memory
334665		limabeans	Bootfall (IZhO17_bootfall)	C++17	100 / 100	359 ms	3796 KiB

bootfall

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 555;



ll sum = 0;
ll dp[maxn*maxn];



void add(ll x) {
    for (int i=sum; i>=0; i--) {
	dp[i+x] += dp[i];
    }
    sum += x;
}


void sub(ll x) {
    for (int i=0; i<=sum; i++) {
	dp[i+x] -= dp[i];
    }
    sum -= x;
}

bool fail[maxn*maxn];

int n;
ll a[maxn];


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);


    dp[0]=1;

    cin>>n;
    for (int i=0; i<n; i++) {
	cin>>a[i];
	add(a[i]);
    }


    if (sum%2) out(0);
    if (dp[sum/2]==0) out(0);


    for (int i=0; i<n; i++) {
	sub(a[i]);
	for (int x=1; x<=500*500; x++) {
	    if ((sum+x)%2==1) {
		fail[x]=true;
	    }
	    if ((sum+x)%2==0 && dp[(sum+x)/2]==0) {
		fail[x]=true;
	    }
	}
	add(a[i]);
    }


    vector<int> ans;
    for (int i=1; i<=500*500; i++) {
	if (!fail[i]) ans.push_back(i);
    }


    cout<<ans.size()<<"\n";
    for (int x: ans) cout<<x<<" ";
    cout<<endl;
    
    
    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