oj.uz

Submission #156209

# Submission time Handle Problem Language Result Execution time Memory
156209 2019-10-04T12:09:40 Z theboatman Bootfall (IZhO17_bootfall) C++17
0 / 100
 2 ms 376 KB 
#include <bits/stdc++.h>

#define y1 theboatman
#define make_struct(args...) {args}

using namespace std;

int main() {
    cin.tie(0);
    ios :: sync_with_stdio(0);

    int n;
    cin >> n;

    int sum = 0;
    vector <int> a(n + 1);

    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
    }

    vector <vector <int> > dp_pref(n + 1, vector <int> (sum * 2 + 1));
    dp_pref[0][sum] = 1;

    vector <set <int> > pref(n + 1);
    pref[0].insert(sum);

    for(int i = 1; i <= n; i++) {
        for(int bal = 0; bal <= sum * 2; bal++) {
            if (dp_pref[i - 1][bal]) {
                dp_pref[i][bal + a[i]] = 1;
                dp_pref[i][bal - a[i]] = 1;
            }
        }

        for(int bal = 0; bal <= sum * 2; bal++) {
            if (dp_pref[i][bal]) {
                pref[i].insert(bal);
            }
        }
    }

    vector <vector <int> > dp_suff(n + 2, vector <int> (sum * 2 + 1));
    dp_suff[n + 1][sum] = 1;

    vector <set <int> > suff(n + 2);
    suff[n + 1].insert(sum);

    for(int i = n; i > 0; i--) {
        for(int bal = 0; bal <= sum * 2; bal++) {
            if (dp_suff[i + 1][bal]) {
                dp_suff[i][bal + a[i]] = 1;
                dp_suff[i][bal - a[i]] = 1;
            }
        }

        for(int bal = 0; bal <= sum * 2; bal++) {
            if (dp_suff[i][bal]) {
                suff[i].insert(bal);
            }
        }
    }

    vector <int> ans;
    for(int power = 1; power <= sum; power++) {
        int ok = 0;
        for(int i = 1; i <= n; i++) {
            for(auto it : pref[i - 1]) {
                //cout << it << endl;
                if (suff[i + 1].find(2 * sum - it - power) != suff[i + 1].end()) {
                    ok++;
                    break;
                }
            }

            if (ok != i) {
                break;
            }
        }

        if (ok == n) {
            ans.push_back(power);
        }
    }

    cout << ans.size() << "\n";
    for(auto i : ans) {
        cout << i << " ";
    }
    return 0;
}
/*
x + power + y - sum == 0

y == sum - x - power

1001
999
*/

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 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 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 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 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 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 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 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 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 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 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -