Submission #1359537

#TimeUsernameProblemLanguageResultExecution timeMemory
1359537vlad7654Kpart (eJOI21_kpart)C++20
100 / 100
412 ms656 KiB
#include <bits/stdc++.h>
using namespace std;
const int NMAX=1e5;
int dp[NMAX+5];
void solve() {
    int n, sz=0;
    cin>>n;
    vector<int> a(n+1), prefix(n+1);
    vector<bool> ans(n+1 ,1);
    for (int i=1;i<=n;i++) {
        cin>>a[i];
        prefix[i]=a[i]+prefix[i-1];
        sz+=a[i];
    }
    sz/=2;
    for (int i=1;i<=sz;i++) {
        dp[i]=INT_MAX;
    }
    for (int i=n;i>=1;i--) {
        dp[0]=i;
        for (int j=sz;j>=a[i];j--) {
            dp[j]=min(dp[j], dp[j-a[i]]);
        }
        for (int j=i;j<=n;j++) {
            int sum=prefix[j]-prefix[i-1];
            bool good=(sum%2==0 and dp[sum/2]<=j);
            ans[j-i+1]=ans[j-i+1]&good;
        }
    }
    cout<<accumulate(ans.begin()+1,ans.end(), 0)<<' ';
    for (int i=1;i<=n;i++) {
        if (ans[i]) {
            cout<<i<<' ';
        }
    }
    cout<<'\n';
}
int main() {
    int t;
    cin>>t;
    while(t--) {
        solve();
    }
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...