Submission #92722

#	Time	Username	Problem	Language	Result	Execution time	Memory
92722		toloraia	Bootfall (IZhO17_bootfall)	C++14	28 / 100	1074 ms	1016 KiB

bootfall

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

const int N = 505, M = 250005;

int n;
int a[N];
bool F[M];
int A[M], B[M];
int np, nn;
int S;
int ANS[M];
int ans[M];

int main()
{
    cin>>n;
    for (int i = 1; i <= n; i++){
        cin>>a[i];
        S += a[i];
    }
    sort (a + 1, a + n + 1);
    bool ok = 0;
    for (int i = 2; i <= n; i++)
        if ((a[i] - a[i - 1]) % 2 == 1)
            ok = 1;
    if (S % 2 == 1)
        ok = 1;
    if (ok){
        cout<<0<<endl;
        return 0;
    }
    F[0] = 1;
    np = 1;
    A[1] = 0;
    for (int i = 1; i <= n; i++){
        nn = 0;
        for (int j = 1; j <= np; j++)
            if (F[A[j] + a[i]] == 0){
                B[++nn] = A[j] + a[i];
                F[B[nn]] = 1;
            }
        for (int j = 1; j <= nn; j++)
            A[++np] = B[j];
    }
    if (F[S / 2] == 0){
        cout<<0<<endl;
        return 0;
    }
    //cout<<S<<endl;
    for (int I = 1; I <= n; I++){
        for (int i = 0; i <= S; i++)
            F[i] = 0;
        F[0] = 1;
        np = 1;
        A[1] = 0;
        for (int i = 1; i <= n; i++){
            if (i == I)
                continue;
            nn = 0;
            for (int j = 1; j <= np; j++)
                if (F[A[j] + a[i]] == 0){
                    B[++nn] = A[j] + a[i];
                    F[B[nn]] = 1;
                }
            for (int j = 1; j <= nn; j++)
                A[++np] = B[j];
        }
        for (int i = 1; i <= S; i++)
            ans[i] = 0;
        for (int i = 1; i <= np; i++){
            ans[abs (S - a[I] - 2 * A[i])] = 1;
            //cout<<I<<" "<<A[i]<<" "<<abs (S - a[I] - 2 * A[i])<<endl;
        }
        for (int i = 1; i <= S; i++)
            ANS[i] += ans[i];
        //cout<<endl;
    }
    np = 0;
    for (int i = 1; i <= S; i++)
        if (ANS[i] == n)
            A[++np] = i;
    cout<<np<<endl;
    for (int i = 1; i <= np; i++)
        cout<<A[i]<<" ";
    cout<<endl;
    return 0;
}

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