Submission #1280671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280671		toplion7	Kpart (eJOI21_kpart)	C++20	10 / 100	2095 ms	572 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e18 + 7;
const int MOD = 998244353;
const int MAXXX = 1000 + 6;
const int OFFSET = 200;

void Make_set(vector<int>& v)
{
    set<int> s(v.begin(), v.end());
    v.assign(s.begin(), s.end());
}

signed main() 
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    for (int K = 0; K < T; K++)
    {
        int n;
        cin >> n;
        int a[n+1];
        for(int i = 1; i <= n; i++)
        {
            cin >> a[i];
        }
        int pr[n+1], cnt = 0, X = a[1];
        pr[0] = 0;
        for(int i = 1; i <= n; i++)
        { 
            pr[i] = pr[i - 1] + a[i];
            if(a[i] == X) cnt++;
        }
        vector<int> ans;
        if(cnt == n)
        {
            for(int k = 2; k <= n; k += 2)
            {
                ans.push_back(k);
            }
        }
        else
        {
            for(int k = 2; k <= n; k++)
            {
                bool V = 1;
                for(int l = 1; l + k - 1 <= n; l++)
                {
                    int r = l + k - 1;
                    int sum = pr[r] - pr[l - 1];
                    if(sum % 2 != 0)
                    {
                        V = 0;
                        break;
                    }
                    int x = sum / 2;
                    vector<bool> dp(x + 1, 0);
                    dp[0] = 1;
                    for (int i = l; i <= r; i++) 
                    {
                        for (int j = x; j >= a[i]; j--)
                        {
                            if (dp[j - a[i]])
                            {
                                dp[j] = 1;
                            }
                        }
                    }
                    if (!dp[x])
                    {
                        V = 0;
                        break;
                    }
                }
                if (V)
                {
                    ans.push_back(k);
                }
            }
        }
        Make_set(ans);
        cout << ans.size();
        for(int i = 0; i < ans.size(); i++)
        {
            cout << " " << ans[i];
        }
        cout << endl;
    }
    return 0;
}

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