Submission #1128179

#TimeUsernameProblemLanguageResultExecution timeMemory
1128179rasbery303Kpart (eJOI21_kpart)C++20
0 / 100
33 ms324 KiB
#include <iostream>
#include <vector>
using namespace std;

const int N = 1001;
int a[N];
bool dp[100001];

void solve(){
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    vector<int> ans;
    int sum = 0, mx = 0;
    for (int i = 1; i <= n; ++i){
        sum += a[i];
        mx = max(mx, a[i]);
        if (sum%2 || i < 2) continue;
        //cout << "sum, i = " << sum << ' ' << i << '\n';

        for (int i = 1; i <= sum; ++i) dp[i] = 0;
        dp[0] = 1;

        for (int j = 1; j <= i; ++j)
            for (int val = mx; val >= a[j]; --val)
                dp[val] |= dp[val-a[j]];
            
        if (dp[sum/i] == 1)
            ans.push_back(i);
        
    }
    cout << ans.size() << ' ';
    for (int& x: ans) cout << x << ' ';
    cout << '\n';

    for (int i = 0; i <= sum; ++i) dp[i] = 0;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int tt;
    cin >> tt;
    while(tt--)
        solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...