175992025-08-08 01:27:29peti1234K-részcpp17Time limit exceeded 30/1001.09s1012 KiB
#include <bits/stdc++.h>
using namespace std;
const int c=100005;
int n, sum, t[c], pref[c], dp[c], rossz[c]; 
vector<int> ans;
void solve() {
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> t[i];
        pref[i]=pref[i-1]+t[i];
        sum+=t[i];
    }

    for (int i=1; i<=n; i++) {
        dp[0]=i;
        for (int j=sum-t[i]; j>=0; j--) {
            dp[j+t[i]]=max(dp[j+t[i]], dp[j]);
        }
        for (int j=1; j<=i; j++) {
            int ert=pref[i]-pref[j-1], len=i-j+1;
            if (ert%2 || dp[ert/2]<j) rossz[len]=1;
        }
    }
    
    for (int i=1; i<=n; i++) {
        if (!rossz[i]) {
            ans.push_back(i);
        }
        rossz[i]=0;
    }

    cout << ans.size() << " ";
    for (auto x:ans) {
        cout << x << " ";
    }
    cout << "\n";

    ans.clear();
    for (int i=0; i<c; i++) dp[i]=0;
    sum=0;
}
int main() {
    ios_base::sync_with_stdio(false);
    int w;
    cin >> w;
    while (w--) {
        solve();
    }
}
SubtaskSumTestVerdictTimeMemory
subtask110/10
1Accepted2ms820 KiB
subtask220/20
1Accepted7ms820 KiB
2Accepted21ms820 KiB
subtask30/70
1Accepted85ms820 KiB
2Accepted229ms1012 KiB
3Accepted263ms820 KiB
4Accepted476ms848 KiB
5Time limit exceeded1.075s820 KiB
6Time limit exceeded1.09s820 KiB
7Time limit exceeded1.087s820 KiB