Submission #675445

#	Time	Username	Problem	Language	Result	Execution time	Memory
675445		LucaIlie	Bootfall (IZhO17_bootfall)	C++17	13 / 100	1090 ms	6152 KiB

bootfall

#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]));

    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: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 0 / 15
• Subtask 4: 0 / 16
• Subtask 5: 0 / 21
• Subtask 6: 0 / 35