Submission #541114

#	Time	Username	Problem	Language	Result	Execution time	Memory
541114		creeped	Bootfall (IZhO17_bootfall)	C++14	100 / 100	396 ms	5788 KiB

bootfall

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

const ll mod = 1e9 + 7;

ll n;
ll a[250002];
ll sum = 0;
ll cnt[250002];
ll mp[250002];

void add(int x) {
	for (int i = sum; i >= 0; i--) {
		cnt[i + x] += cnt[i];
		if (cnt[i + x] >= mod) cnt[i + x] -= mod;
	}
	sum += x;
}

void sub(int x) {
	for (int i = 0; i <= sum; i++) {
		cnt[i + x] += (mod - cnt[i]);
		if (cnt[i + x] >= mod) cnt[i + x] -= mod;
	}
	sum -= x;
}


int main() {

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

    if(sum&1 || !cnt[sum/2])
    {
        cout<<"0\n";
        return 0;
    }

    for(ll i=1;i<=n;i++)
    {
        sub(a[i]);
        ll v = 2;
        if(sum & 1)
            v--;
        for(ll j=v; j<=sum; j+=2)
            if(cnt[(sum + j) / 2 - j])
                mp[j] ++;
                
        add(a[i]);
    }
    vector<ll> ans;
    for(ll i=1;i<=sum;i++)
        if(mp[i] == n)
            ans.push_back(i);
    cout<<ans.size()<<endl;
    for(auto it:ans)
        cout<<it<<" ";
    cout<<endl;
}

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