Submission #1236759

#TimeUsernameProblemLanguageResultExecution timeMemory
1236759wedonttalkanymoreKpart (eJOI21_kpart)C++20
100 / 100
786 ms892 KiB
#include <bits/stdc++.h>
using namespace std;
int n, a[100005], pfs[100005], dp[100005], check[100005];

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

    int t; 
    cin >> t;
    while(t--){
        cin >> n;
        int sum = 0;
        for(int i = 1; i <= n; i++){
            cin >> a[i];
            check[i] = 1;
            sum += a[i];
            pfs[i] = pfs[i-1] + a[i];
        }
        for(int s = 0; s <= sum; s++) dp[s] = 0;
        for(int j = 1; j <= n; j++){
            for(int s = sum; s >= a[j]; s--) dp[s] = max(dp[s], dp[s - a[j]]);
            dp[a[j]] = j;
            for(int i = j; i >= 1; i--){
                int T = pfs[j] - pfs[i-1];
                int len = j - i + 1;
                if (T % 2 || dp[T/2] < i) check[len] = 0;
            }
        }
        vector<int> ans;
        for(int i = 1; i <= n; i++) if (check[i]) ans.push_back(i);
        cout << ans.size();
        for(int x: ans) cout << ' ' << x;
        cout << '\n';
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...