Submission #1025149

#TimeUsernameProblemLanguageResultExecution timeMemory
1025149coolboy19521Kpart (eJOI21_kpart)C++17
100 / 100
1063 ms1512 KiB
#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();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...