제출 #1337707

#제출 시각아이디문제언어결과실행 시간메모리
1337707aaaaaaaaKpart (eJOI21_kpart)C++20
100 / 100
1008 ms199676 KiB
#include <bits/stdc++.h>
using namespace std;

const int mxN = 1e3 + 3;
const int mxS = 1e5 + 5;

int a[mxN], p[mxN], dp[mxN][mxS];

void testCase(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        p[i] = p[i - 1] + a[i];
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= (p[n] >> 1); ++j){
            if(j == a[i]) dp[i][j] = i;
            else if(j >= a[i]) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a[i]]);
            else dp[i][j] = dp[i - 1][j];
        }
    }
    vector<int> ans;
    for(int len = 2; len <= n; ++len){
        bool flag = 1;
        for(int i = 1; i <= n - len + 1; ++i){
            int sum = p[i + len - 1] - p[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...