제출 #1280610

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

#define pb push_back
#define int long long

const int N = 1e6+10;
const int inf = 1e18;

signed main() {         
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--) {
        int n;
        cin>>n;
        int a[n+1];
        int pref[n+1];
        pref[0]=0;
        for(int i=1;i<=n;i++) {
            cin>>a[i];
            pref[i]=pref[i-1]+a[i];
        }
        vector<int>ans;
        for(int len=2;len<=n;len++) {
            int maybe=0;
            for(int i=len;i<=n;i++) {
                int sum=(pref[i]-pref[(i-len)]);
                if(sum%2==1) continue;
                bool dp[n+1];
                sum/=2;
                dp[0]=1;
                for(int j=1;j<=sum;j++) {
                    for(int k=len-i+1;k<=i;k++) {
                        if(a[k]>j) continue;
                        dp[j]=max(dp[j],dp[j-a[k]]);
                    }
                }
                if(dp[sum]) {
                    maybe++;
                }
            }
            if(maybe==n-(len-1)) ans.pb(len);
        }
        cout<<ans.size()<<' ';
        for(auto it:ans) cout<<it<<' ';
        cout<<"\n";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...