Submission #1225011

#TimeUsernameProblemLanguageResultExecution timeMemory
1225011khomeKpart (eJOI21_kpart)C++20
10 / 100
2096 ms436 KiB
#include <bits/stdc++.h>
using namespace std;

bool check(vector<int> &v, int l, int r)
{
    int cnt = 0;
    vector<int> a;
    for (int i = l; i <= r; i++)
    {
        // cout << v[i] << ' ';
        a.push_back(v[i]);
        cnt += v[i];
    }
    // cout << endl;

    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];
}

void solve()
{
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    vector<int> ans;
    for (int k = 2; k <= n; k++)
    {
        // cout << k << endl;
        bool so = true;
        for (int l = 0; l <= n - k; l++)
        {
            if (!check(v, l, l + k - 1))
            {
                so = false;
                break;
            }
        }
        if (so)
            ans.push_back(k);
    }
    cout << ans.size() << ' ';
    for (int i : ans)
        cout << i << ' ';
    cout << endl;
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
        solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...