oj.uz

Submission #92752

# Submission time Handle Problem Language Result Execution time Memory
92752 2019-01-04T12:53:44 Z toloraia Bootfall (IZhO17_bootfall) C++14
0 / 100
 2 ms 376 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 505, M = 260010;
const ll B = 1e18;

int n;
int a[N];
bool F[M], f[M];
int S;
ll DP[M][10];
ll dp[M][10];
int ans[M], ANS[M];
vector < int > V, v;

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;
    DP[0][0] = 1;
    for (int i = 1; i <= n; i++){
        for (int j = S; j >= a[i]; j--)
            if (F[j - a[i]]){
                F[j] = 1;
                for (int l = 0; l < 9; l++){
                    DP[j][l] += DP[j - a[i]][l];
                    if (DP[j][l] >= B){
                        DP[j][l + 1]++;
                        DP[j][l] -= B;
                    }
                }
            }
    }
    if (F[S / 2] == 0){
        cout<<0<<endl;
        return 0;
    }
    for (int i = 0; i <= S; i++)
        if (F[i])
            V.push_back (i);
    for (int I = 1; I <= n; I++){
        for (int i1 = 0; i1 < (int)V.size(); i1++){
            int i = V[i1];
            for (int j = 0; j < 9; j++)
                dp[i][j] = DP[i][j];
        }
        memset(ans, 0, S + 5);
        for (int i1 = 0; i1 < (int)V.size(); i1++){
            int i = V[i1];
                f[i] = 1;
                if (i >= a[I]){
                    f[i] = 0;
                    for (int j = 0; j < 9; j++){
                        dp[i][j] -= dp[i - a[I]][j];
                        if (dp[i][j] < 0){
                            dp[i][j] += B;
                            dp[i][j + 1]--;
                        }
                        if (dp[i][j])
                            f[i] = 1;
                    }
                }
                if (f[i] && ans[abs (S - a[I] - 2 * i)] == 0){
                    ans[abs (S - a[I] - 2 * i)] = 1;
                    ANS[abs (S - a[I] - 2 * i)]++;
                }
            }
    }
    V.clear();
    for (int i = 1; i <= S; i++)
        if (ANS[i] == n)
            V.push_back (i);
    cout<<(int)V.size()<<endl;
    for (int i = 0; i < (int)V.size(); i++)
        cout<<V[i]<<" ";
    cout<<endl;
    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -