oj.uz

Submission #340371

# Submission time Handle Problem Language Result Execution time Memory
340371 2020-12-27T13:31:13 Z balanda Bootfall (IZhO17_bootfall) C++17
13 / 100
 16 ms 492 KB 
/*
             _   _                    _           _                 _         __   _____ _____ _
            | | | |               _  | |         | |               | |       /  | |____ |  ___(_)
  __ _ _   _| |_| |__   ___  _ __(_) | |__   __ _| | __ _ _ __   __| | __ _  `| |     / /___ \ _  __ _
 / _` | | | | __| '_ \ / _ \| '__|   | '_ \ / _` | |/ _` | '_ \ / _` |/ _` |  | |     \ \   \ \ |/ _` |
| (_| | |_| | |_| | | | (_) | |   _  | |_) | (_| | | (_| | | | | (_| | (_| | _| |_.___/ /\__/ / | (_| |
 \__,_|\__,_|\__|_| |_|\___/|_|  (_) |_.__/ \__,_|_|\__,_|_| |_|\__,_|\__,_| \___/\____/\____/|_|\__, |
                                                                                                    | |
                                                                                                    |_|
  __ _  __ _   _ __ ___   __ ___   _________  ___
 / _` |/ _` | | '_ ` _ \ / _` \ \ / /_  / _ \/ __|
| (_| | (_| | | | | | | | (_| |\ V / / /  __/\__ \
 \__, |\__, | |_| |_| |_|\__,_| \_/ /___\___||___/
    | |   | |
    |_|   |_|
 * */
#include <bits/stdc++.h>

using namespace std;
#define endl '\n'
#define int long long

template<class T>
istream& operator>>(istream &in, vector<T> &v){
    for(auto &to: v) in >> to;
    return in;
}

template<class T>
ostream& operator<<(ostream &out, const vector<T> &v){
    for(auto &to: v) out << v << ' ';
    return out;
}


template<class U, class V>
istream& operator>>(istream &in, pair<U, V> &v){
    in >> v.first >> v.second;
    return in;
}

template<class U, class V>
ostream& operator<<(ostream &out, const pair<U, V> &v){
    out << v.first << ' ' << v.second;
    return out;
}

#ifdef DEBUG
#define dbg(x) cout << "debug:" << __LINE__ << ' ' << #x << "=" << x
#else
#define dbg(x) 42
#endif

int solve(){
    int n;
    cin >> n;
    vector<int> v(n);
    cin >> v;
    int sm = 0;
    for(int i = 0; i < n; i++)
        sm += v[i];
    vector<bitset<2505> > dpp(n + 1);
    vector<bitset<2505> > dps(n + 1);
    dpp[0][0] = 1;
    dps[n][0] = 1;
    for(int i = 1; i <= n; i++){
       dpp[i] = dpp[i - 1];
       dpp[i] |= (dpp[i - 1] << v[i - 1]);
    }
    for(int i = n - 1; i >= 0; i--){
        dps[i] = dps[i + 1];
        dps[i] |= (dps[i + 1] << v[i]);
    }
    if(!dpp[n][sm / 2]){
        cout << 0;
        return 0;
    }
    set<int> possible;
    for(int j = 1; j < 2505; j++) {
        possible.insert(j);
    }
    for(int i = 0; i < n; i++){
        bitset<2505> crr;
        for(int j = 0; j < 2505; j++){
            if(dpp[i][j])
                crr |= (dps[i + 1] << j);
        }
        vector<int> bad;
        for(auto to: possible){
            int full = (sm - v[i] + to);
            if(full % 2) bad.push_back(to);
            else if(!(crr[full / 2] && crr[full / 2 - to])){
                bad.push_back(to);
            }
        }
        for(auto to: bad) possible.erase(to);
    }
    cout << possible.size() << endl;
    for(auto to: possible){
        cout << to << ' ';
    }
    return 0;
}
signed main() {
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
//        freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
//    cin >> t;
    while(t  --> 0){
        assert(solve() == 0);
        cout << endl;
    }
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 2 ms 492 KB Output is correct
12 Correct 2 ms 492 KB Output is correct
13 Correct 2 ms 492 KB Output is correct
14 Correct 2 ms 492 KB Output is correct
15 Correct 2 ms 492 KB Output is correct
16 Correct 2 ms 492 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 2 ms 492 KB Output is correct
19 Correct 2 ms 492 KB Output is correct
20 Correct 1 ms 492 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 2 ms 492 KB Output is correct
12 Correct 2 ms 492 KB Output is correct
13 Correct 2 ms 492 KB Output is correct
14 Correct 2 ms 492 KB Output is correct
15 Correct 2 ms 492 KB Output is correct
16 Correct 2 ms 492 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 2 ms 492 KB Output is correct
19 Correct 2 ms 492 KB Output is correct
20 Correct 1 ms 492 KB Output is correct
21 Incorrect 16 ms 492 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 2 ms 492 KB Output is correct
12 Correct 2 ms 492 KB Output is correct
13 Correct 2 ms 492 KB Output is correct
14 Correct 2 ms 492 KB Output is correct
15 Correct 2 ms 492 KB Output is correct
16 Correct 2 ms 492 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 2 ms 492 KB Output is correct
19 Correct 2 ms 492 KB Output is correct
20 Correct 1 ms 492 KB Output is correct
21 Incorrect 16 ms 492 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 2 ms 492 KB Output is correct
12 Correct 2 ms 492 KB Output is correct
13 Correct 2 ms 492 KB Output is correct
14 Correct 2 ms 492 KB Output is correct
15 Correct 2 ms 492 KB Output is correct
16 Correct 2 ms 492 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 2 ms 492 KB Output is correct
19 Correct 2 ms 492 KB Output is correct
20 Correct 1 ms 492 KB Output is correct
21 Incorrect 16 ms 492 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 2 ms 492 KB Output is correct
12 Correct 2 ms 492 KB Output is correct
13 Correct 2 ms 492 KB Output is correct
14 Correct 2 ms 492 KB Output is correct
15 Correct 2 ms 492 KB Output is correct
16 Correct 2 ms 492 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 2 ms 492 KB Output is correct
19 Correct 2 ms 492 KB Output is correct
20 Correct 1 ms 492 KB Output is correct
21 Incorrect 16 ms 492 KB Output isn't correct
22 Halted 0 ms 0 KB -