제출 #1299776

#제출 시각아이디문제언어결과실행 시간메모리
1299776uroskKpart (eJOI21_kpart)C++17
100 / 100
1364 ms195988 KiB
// __builtin_popcount(x) broj bitova
// __builtin_popcountll(x)
// __builtin_clz(x) vodece nule
// __builtin_clzll(x)
// __builtin_ctz(x) nule na pocetku
// __builtin_ctzll(x)
// 2000000011
// 2000000033
#include "bits/stdc++.h"

using namespace std;

#define maxn 1005
#define maxs 50005
int a[maxn];
int pref[maxn];
int dp[maxn][maxs];
int n;
void tc(){
    cin >> n;
    for(int i = 1;i<=n;i++) cin >> a[i];
    for(int i = 0;i<=n;i++) fill(dp[i],dp[i]+maxn-1,0); ///initialize to 0 (if dp[i][s] = 0 it means that we cant make sum s with first i elements)
    for(int i = 1;i<=n;i++) pref[i] = pref[i-1] + a[i];
    for(int i = 1;i<=n;i++){
        for(int s = 0;s<=maxs-5;s++){
            dp[i][s] = dp[i-1][s];
            if(s>a[i]) dp[i][s] = max(dp[i][s],dp[i-1][s-a[i]]);
            if(s==a[i]) dp[i][s] = i;
        }
    }
    vector<int> ans;
    for(int k = 2;k<=n;k++){
        bool ok = 1;
        for(int r = k;r<=n;r++){
            int l = r-k+1;
            int sum = pref[r]-pref[l-1];
            if(sum&1) ok = 0;
            if(dp[r][sum/2]<l) ok = 0;
        }
        if(ok) ans.push_back(k);
    }
    cout<<ans.size()<<" ";
    for(int x : ans) cout<<x<< " ";
    cout<<endl;
}
int main(){
    int t; cin >> t;
    while(t--) tc();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...