Submission #1025149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025149		coolboy19521	Kpart (eJOI21_kpart)	C++17	100 / 100	1063 ms	1512 KiB

Main

#include "bits/stdc++.h"
#define int long long

using namespace std;

const int sz = 1e3 + 3;
const int sm = 1e5 + 5;

bool r[sz];
int dp[sm];
int a[sz];

void solve() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i ++)
        cin >> a[i];

    fill_n(r, n + 1, true);
    fill_n(dp, sm, 0);

    for (int i = 1; i <= n; i ++) {
        for (int j = sm - 1; a[i] <= j; j --)
            dp[j] = max(dp[j], dp[j - a[i]]);
        dp[0] = dp[a[i]] = i;
        int sm = 0;
        for (int j = i; 1 <= j; j --) {
            sm += a[j];
            if (sm & 1 || dp[sm / 2] < j)
                r[i - j + 1] = false;
        }
    }

    vector<int> an;

    for (int i = 1; i <= n; i ++)
        if (r[i]) an.push_back(i);

    cout << an.size();
    for (int x : an)
        cout << ' ' << x;
    cout << '\n';
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int t;
    cin >> t;

    while (t --)
        solve();
}

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