Submission #543663

#TimeUsernameProblemLanguageResultExecution timeMemory
543663tudorKpart (eJOI21_kpart)C++17
100 / 100
623 ms684 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...