Submission #626180

#	Time	Username	Problem	Language	Result	Execution time	Memory
626180		Blagoj	Kpart (eJOI21_kpart)	C++14	10 / 100	2089 ms	324 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
int a[1001], total = 0;
bool solve(int l, int r)
{
    bool dp[total / 2 + 1];
    memset(dp, false, total / 2 + 1);
    dp[0] = true;
    int mx = 0;
    for (int i = l; i <= r; i++)
    {
        for (int j = mx; j >= 0; j--)
        {
            if (dp[j] && (j + a[i]) * 2 <= total)
            {
                if ((j + a[i]) * 2 == total)
                {
                    return true;
                }
                dp[j + a[i]] = true;
                mx = max(mx, j + a[i]);
            }
        }
    }
    return false;
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin >> t;
    int n;
    bool possible = true;
    while (t--)
    {
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
        vector<int> v;
        for (int sz = 2; sz <= n; sz++)
        {
            possible = true;
            total = 0;
            for (int i = 0; i < sz; i++)
            {
                total += a[i];
            }
            for (int i = 0; i + sz <= n; i++)
            {
                if (i > 0)
                {
                    total -= a[i - 1];
                    total += a[i + sz - 1];
                }
                if (!solve(i, i + sz - 1))
                {
                    possible = false;
                    break;
                }
            }
            if (possible)
            {
                v.push_back(sz);
            }
        }
        cout << v.size() << " ";
        for (auto x : v)
        {
            cout << x << " ";
        }
        cout << "\n";
    }
}

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