oj.uz

Submission #543663

# Submission time Handle Problem Language Result Execution time Memory
543663 2022-03-31T07:58:06 Z tudor Kpart (eJOI21_kpart) C++17
100 / 100
 623 ms 684 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 11 ms 468 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 504 KB Output is correct
2 Correct 115 ms 524 KB Output is correct
3 Correct 130 ms 528 KB Output is correct
4 Correct 239 ms 548 KB Output is correct
5 Correct 453 ms 544 KB Output is correct
6 Correct 623 ms 584 KB Output is correct
7 Correct 543 ms 684 KB Output is correct