Submission #1318323

#TimeUsernameProblemLanguageResultExecution timeMemory
1318323jesusargKpart (eJOI21_kpart)C++20
30 / 100
834 ms84752 KiB
#include <bits/stdc++.h>
#define pb push_back 
using namespace std;
short dp[1001][50002];
int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<int> v(n),pref(n+1,0);
        int tot=0;
        for(auto&i:v)cin>>i,tot+=i;
        for(int i = 0; i <= n; i++){
            for(int j = 0; j <= ceil(tot/2); j++){
                dp[i][j]=-1; 
            }
        }
        for(int i = 0; i < n; i++){
            pref[i+1]=pref[i]+v[i];
            dp[i+1][v[i]]=i+1;
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= pref[i]; j++){
                dp[i][j]=max({dp[i][j],dp[i-1][j]});
                if(v[i-1]<j){
                    dp[i][j] = max(dp[i][j], dp[i-1][j-v[i-1]]);
                }
            }
        }
        vector<int> ans;
        for(int i = 1; i <= n; i++){
            bool ok=1;
            for(int j = i; j <= n; j++){
                int sum=pref[j]-pref[j-i];
                if(sum&1){
                    ok=0;break;
                }
                if(dp[j][sum/2] < (j-i+1)){
                    ok=0;break;
                }
            }
            if(ok) ans.pb(i);
        }
        cout << ans.size() << ' ';
        for(auto i : ans) cout << i << ' ';
        cout << '\n';
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...