제출 #1280629

#제출 시각아이디문제언어결과실행 시간메모리
1280629bnijaamaaKpart (eJOI21_kpart)C++20
10 / 100
2094 ms572 KiB
#include <bits/stdc++.h>

#define nn '\n'
#define int long long
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define vec vector

using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n), p(n + 1);
        for (int i = 0; i < n; ++i) cin >> a[i];
        for (int i = 0; i < n; ++i) p[i + 1] = p[i] + a[i];
        vec<int> res;
        for (int i = 2; i <= n; ++i) {
            bool ok = true;
            for (int j = 0; j + i <= n; ++j) {
                int r = i + j;
                int sum = p[r] - p[j];
                if (sum % 2 != 0) {
                    ok = false;
                    break;
                }
                int cnt = sum / 2;
                vector<bool> dp(cnt + 1, false);
                dp[0] = true;
                for (int k = j; k < r; ++k) {
                    for (int h = cnt; h >= a[k]; --h) {
                        if (dp[h - a[k]] ) {
                            dp[h] = true;
                        }
                    }
                }
                if (!dp[cnt]) {
                    ok = false;
                    break;
                }
            }
            if (ok) res.pb(i);
        }
        cout << res.size();
        for (int x : res) cout << ' ' << x;
        cout << nn;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...