oj.uz

Submission #675444

# Submission time Handle Problem Language Result Execution time Memory
675444 2022-12-27T09:13:28 Z LucaIlie Bootfall (IZhO17_bootfall) C++17
0 / 100
 1 ms 1108 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxN = 500;
const int maxS = 500 * 500;

int v[maxN + 1];
bitset<maxS + 1> pos1n[maxN + 1], posn1[maxN + 2];
bitset<maxS + 1> pos, tim, timTemp;

int main() {
    int n, s = 0;

    cin >> n;
    for ( int i = 1; i <= n; i++ )
        cin >> v[i], s += v[i];

    pos1n[0][0] = true;
    for ( int i = 1; i <= n; i++ )
        pos1n[i] = (pos1n[i - 1] | (pos1n[i - 1] << v[i]));
    posn1[n + 1][0] = true;
    for ( int i = n; i >= 1; i-- )
        posn1[i] = (posn1[i + 1] | (posn1[i + 1] << v[i]));

    cout << pos1n[n] << "\n";
    if ( s % 2 != 0 || !pos1n[n][s / 2] ) {
        cout << 0;
        return 0;
    }

    for ( int i = 0; i <= s; i++ )
        tim[i] = true;
    for ( int r = 1; r <= n; r++ ) {
        pos = pos1n[r - 1];
        for ( int i = 0; i <= s; i++ ) {
            if ( posn1[r + 1][i] )
                pos |= (pos1n[r - 1] << i);
        }

        timTemp.reset();
        for ( int i = 0; i <= s; i++ ) {
            if ( pos[i] )
                timTemp[abs( s - v[r] - i - i )] = true;
        }
        tim &= timTemp;
    }

    tim[0] = false;
    cout << tim.count() << "\n";
    for ( int i = 0; i <= s; i++ ) {
        if ( tim[i] )
            cout << i << " ";
    }

    return 0;
}

Subtask #1
0 / 6.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 16.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 35.0

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