Submission #556127

#	Time	Username	Problem	Language	Result	Execution time	Memory
556127		Skurrl	Kpart (eJOI21_kpart)	C++17	0 / 100	1 ms	468 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define N 100005
#define MOD 1000000007
#define endl '\n'
#define all(x) x.begin(), x.end()

typedef long long int ll;

const ll inf = 1e17;

void solve()
{
    int n; cin >> n;
    vector<int> arr(n + 1);

    for(int i = 1; i <= n; ++i) cin >> arr[i];

    vector<int> ks;

    for (int k = 1; k <= n; ++k)
    {
        bool ok = true;
        for (int i = 1; i <= n - k + 1; ++i)
        {
            int sum = 0;

            for(int j = i; j < i + k; ++j) 
                sum += arr[j];

            if(!(sum & 1))
            {
                vector<bool> part(sum / 2 + 1);

                for (int j = i; j < i + k; ++j)
                {
                    for(int l = sum / 2; l >= 0; --l)
                    {
                        if(part[l - arr[j]] == 1 or l == arr[j]) part[l] = true;
                    }
                }

                ok &= part[sum / 2];
            }

            ok &= (sum % 2 == 0);
        }

        if(ok) ks.pb(k);
    }

    cout << ks.size() << " ";
    for(auto i : ks) cout << i << " ";

    cout << endl;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll t; cin >> t;
    while(t--)
        solve();
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 70