Submission #1280621

#TimeUsernameProblemLanguageResultExecution timeMemory
1280621bnijaamaaKpart (eJOI21_kpart)C++20
10 / 100
2095 ms648 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);
        for (int i = 0; i < n; ++i) cin >> a[i];
        vector<int> res;
        for (int i = 2; i <= n; ++i) {
            bool ok = true;
            for (int j = 0; j + i <= n; ++j) {
                vector<int> v(a.begin() + j, a.begin() + i + j);
                int sum = accumulate(all(v), 0LL);
                if (sum % 2 != 0) {
                    ok = false;
                    break;
                }
                int cnt = sum / 2;
                vector<bool> dp(cnt + 1, false);
                dp[0] = true;
                for (int l = 0 ; l < v.size(); l++) {
                    for (int k = cnt; k >= v[l]; --k) {
                        if (dp[k - v[l]]) dp[k] = 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...