제출 #1329033

#제출 시각아이디문제언어결과실행 시간메모리
1329033kawhietKpart (eJOI21_kpart)C++20
10 / 100
2094 ms488 KiB
#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> p(n + 1);
    for (int i = 0; i < n; i++) {
        p[i + 1] = p[i] + a[i];
    }
    auto good = [&](int k) {
        for (int i = 0; i + k <= n; i++) {
            int s = p[i + k] - p[i];
            vector<int> dp(s + 1, 0);
            dp[0] = 1;
            for (int j = i; j < i + k; j++) {
                for (int u = s; u >= a[j]; u--) {
                    if (dp[u - a[j]]) {
                        dp[u] = 1;
                    }
                }
            }
            if (s % 2 == 1 || !dp[s / 2]) {
                return false;
            }
        }
        return true;
    };
    vector<int> ans;
    for (int i = 1; i <= n; i++) {
        if (good(i)) {
            ans.push_back(i);
        }
    }
    cout << ans.size() << ' ';
    for (auto i : ans) {
        cout << i << ' ';
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    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...