Submission #541113

#	Time	Username	Problem	Language	Result	Execution time	Memory
541113		creeped	Bootfall (IZhO17_bootfall)	C++14	13 / 100	1 ms	340 KiB

bootfall

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll a[250002];
ll sum = 0;
ll cnt[250002];
ll mp[250002];

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

void sub(ll x)
{
    for(ll i=0;i<=sum; i++)
        cnt[i+x] = max(cnt[i+x] - cnt[i], 0LL);
    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: 0 / 15
• Subtask 4: 0 / 16
• Subtask 5: 0 / 21
• Subtask 6: 0 / 35