Submission #543663

#	Time	Username	Problem	Language	Result	Execution time	Memory
543663		tudor	Kpart (eJOI21_kpart)	C++17	100 / 100	623 ms	684 KiB

Main

#include <iostream>
#include <vector>

using namespace std;
const int smax = 5e4;
const int nmax = 1e3;

int p[smax + 1];
int s[nmax + 1];
vector < int > sol[2];

void solve () {
    sol[0].clear ();
    sol[1].clear ();
    s[0] = p[0] = 0;
    for ( int i = 1; i <= smax; i++ )
        p[i] = -1;

    int n, x;
    cin >> n;
    for ( int i = 1; i <= n; i++ ) {
        cin >> x;
        s[i] = s[i - 1] + x;
        for ( int j = min ( s[i], smax ) - x; j >= 0; j-- )
            p[j + x] = max ( p[j + x], p[j] );
        if ( x <= smax )
            p[x] = i;

        sol[i % 2].clear ();
        sol[1 - i % 2].push_back ( i );
        int sum;
        for ( auto x: sol[1 - i % 2] )
            if ( ( sum = ( s[i] - s[i - x] ) ) % 2 == 0 && p[sum / 2] >= i - x + 1 )
                sol[i % 2].push_back ( x );
    }

    cout << sol[n % 2].size () << ' ';
    for ( auto x: sol[n % 2] )
        cout << x << ' ';
    cout << '\n';
}



int main() {
    int t;
    cin >> t;
    while ( t-- )
        solve ();

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70