제출 #1342969

#제출 시각아이디문제언어결과실행 시간메모리
1342969uranhishigKpart (eJOI21_kpart)C++20
10 / 100
2095 ms440 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long

vector<int> v, p;

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

signed main(){
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        v.resize(n);
        p.resize(n + 1, 0);
        for (int i = 0; i < n; i++) {
            cin >> v[i];
            p[i + 1]=p[i] + 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...