Submission #1337703

#TimeUsernameProblemLanguageResultExecution timeMemory
1337703aaaaaaaaKpart (eJOI21_kpart)C++20
30 / 100
2096 ms321528 KiB
#include <bits/stdc++.h>
using namespace std;

void testCase(){
    int n, total = 0;
    cin >> n;
    vector<int> a(n + 1, 0);
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        total += a[i];
    }
    vector<vector<int>> dp(n + 5, vector<int>(total + 5, 0));
    total /= 2;
    for(int i = 1; i <= n; ++i){
        dp[i][a[i]] = i;
        for(int j = 1; j <= total; ++j){
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);
            if(a[i] <= j) dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i]]);
        }
    }
    for(int i = 1; i <= n; ++i) a[i] += a[i - 1];
    vector<int> ans;
    for(int len = 2; len <= n; ++len){
        bool flag = 1;
        for(int i = 1; i <= n - len + 1; ++i){
            int sum = a[i + len - 1] - a[i - 1];
            if(sum & 1 || dp[i + len - 1][sum >> 1] < i){
               flag = 0;
               break;
            }
        }
        if(flag) ans.push_back(len);
    }
    cout << (int) ans.size() << " ";
    for(auto x : ans) cout << x << " ";
    cout << "\n";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int tc;
    cin >> tc;
    while(tc--) testCase();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...