Submission #1336831

#TimeUsernameProblemLanguageResultExecution timeMemory
1336831maharramKpart (eJOI21_kpart)C++20
30 / 100
2096 ms319864 KiB
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
#define pb push_back
#define ff first
#define ss second
#define sorta sort(a,a+n)
#define reversea reverse(a,a+n)
#define all(x) x.begin(), x.end()
#define hurryup ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
const int INF=1e18;


signed main() {
    hurryup;
    int t;
    cin>>t;
    while(t--) {
        int n;
        cin>>n;
        int a[n+1], pre[n+1]; pre[0]=0;
        for(int i=1; i<=n; i++) {
            cin>>a[i];
            pre[i]=pre[i-1]+a[i];
        }
        vector<vector<int>> dp(n+1,vector<int> (pre[n]/2+1));
        for(int i=1; i<=n; i++) {
            for(int c=1; c<=pre[n]/2; c++) {
                dp[i][c]=dp[i-1][c];
                if(a[i]==c) {
                    dp[i][c]=i;
                }
                if(c-a[i]>=1) {
                    dp[i][c]=max(dp[i][c],dp[i-1][c-a[i]]);
                }
            }
        }
        vector<int> res;
        for(int sz=2; sz<=n; sz++) {
            bool ok=true;
            for(int l=1; l<=n-sz+1; l++) {
                int r=l+sz-1;
                int sum=pre[r]-pre[l-1];
                assert(r-l+1==sz);
                if(sum%2==1 || dp[r][sum/2]<l) {  
                    ok=false;
                    break;
                }
            }
            if(ok) res.pb(sz);
        }
        cout<<res.size()<<' ';
        for(int i:res) cout<<i<<' ';
        cout<<'\n';
    }

}
// by Maharram Gurbanzada




























#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...