Submission #617208

#	Time	Username	Problem	Language	Result	Execution time	Memory
617208		Hanksburger	Bootfall (IZhO17_bootfall)	C++17	100 / 100	327 ms	2884 KiB

bootfall

#include <bits/stdc++.h>
using namespace std;
int g[250005], f[250005], a[505];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, sum=0, ans=0;
    cin >> n;
    f[0]=1;
    for (int i=1; i<=n; i++)
    {
        cin >> a[i];
        for (int j=sum; j>=0; j--)
            f[j+a[i]]+=f[j];
        sum+=a[i];
    }
    for (int i=1; i<=n; i++)
    {
        sum-=a[i];
        for (int j=0; j<=sum; j++)
        {
            f[j+a[i]]-=f[j];
            if (f[j])
                g[max(0, j*2-sum)]++;
        }
        for (int j=sum; j>=0; j--)
            f[j+a[i]]+=f[j];
        sum+=a[i];
    }
    if (sum&1 || !f[sum/2])
    {
        cout << 0;
        return 0;
    }
    for (int i=1; i<=sum; i++)
        if (g[i]==n)
            ans++;
    cout << ans << '\n';
    for (int i=1; i<=sum; i++)
        if (g[i]==n)
            cout << i << ' ';
    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