제출 #1280661

#제출 시각아이디문제언어결과실행 시간메모리
1280661toplion7Kpart (eJOI21_kpart)C++20
0 / 100
2095 ms2564 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e18 + 7;
const int MOD = 998244353;
const int MAXXX = 20 + 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;
    // T = 1;
    for (int K = 0; K < T; K++)
    {
        int n;
        cin >> n;
        int MX = 0;
        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)
        {
            ans.push_back(2);
        }
        
        for(int k = 3; k <= n; k++)
        {
            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)
                {
                    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]) 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;
}


#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...