Submission #1342950

#TimeUsernameProblemLanguageResultExecution timeMemory
1342950uranhishigKpart (eJOI21_kpart)C++20
10 / 100
2096 ms440 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long

vector<int> v;

bool check(int l, int r){
    int cnt = 0;
    vector<int> a;
    for (int i = l; i <= r; i++) {
        a.push_back(v[i]);
        cnt += v[i];
    }
    if (cnt % 2 == 1) return false;
    cnt /= 2;
    vector<bool> dp(cnt + 1);
    dp[0] = true;
    for (int i : a){
        for (int j = cnt; j >= i; j--){
            if (dp[j - i]) dp[j] = true;
        }
    }
    return dp[cnt];
}

signed main(){
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        v.resize(n);
        for (int i = 0; i < n; i++) {
            cin >> v[i];
        }
        vector<int> ans;
        for (int k = 2; k <= n; k++) {
            bool ok = true;
            for (int l = 0; l <= n - k; l++) {
                if (!check(l, l + k - 1)) {
                    ok = false;
                    break;
                }
            }
            if (ok == true) ans.push_back(k);
        }
        cout << ans.size() << ' ';
        for (int X : ans) cout << X << ' ';
        cout << endl;
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...