Submission #92782

#	Time	Username	Problem	Language	Result	Execution time	Memory
92782		toloraia	Bootfall (IZhO17_bootfall)	C++14	65 / 100	1081 ms	4604 KiB

bootfall

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

const int N = 505, M = 260010;
const int B = 1e9 + 7;

int n;
int a[N];
bool F[M], f;
int S;
int DP[M];
int dp[M];
int ans[M], ANS[M];
int V[M], np;
int i, j, i1;
int main()
{
    cin>>n;
    for (i = 1; i <= n; i++){
        cin>>a[i];
        S += a[i];
    }
    sort (a + 1, a + n + 1);
    bool ok = 0;
    for (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;
    DP[0] = 1;
    for (i = 1; i <= n; i++){
        for (j = S; j >= a[i]; j--)
            if (F[j - a[i]]){
                F[j] = 1;
                DP[j] += DP[j - a[i]];
                if (DP[j] > B)
                    DP[j] -= B;
            }
    }
    if (F[S / 2] == 0){
        cout<<0<<endl;
        return 0;
    }
    for (i = 0; i <= S; i++)
        if (F[i])
            V[np++] = i;
    for (int I = 1; I <= n; ++I){
        for (i1 = 0; i1 < np; ++i1){
            i = V[i1];
            dp[i] = DP[i];
            ans[abs (S - 2 * i - a[I])] = 0;
        }
        for (i1 = 0; i1 < np; ++i1){
            i = V[i1];
                f = 1;
                if (i >= a[I]){
                    f = 0;
                        dp[i] -= dp[i - a[I]];
                        if (dp[i] < 0)
                            dp[i] += B;
                        if (dp[i])
                            f = 1;
                }
                if (f && ans[abs (S - a[I] - 2 * i)] == 0){
                    ans[abs (S - a[I] - 2 * i)] = 1;
                    ANS[abs (S - a[I] - 2 * i)]++;
                }
            }
    }
    np = 0;
    for (i = 1; i <= S; i++)
        if (ANS[i] == n)
            V[np++] = i;
    cout<<np<<endl;
    for (i = 0; i < np; i++)
        cout<<V[i]<<" ";
    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: 0 / 35