제출 #1300737

#제출 시각아이디문제언어결과실행 시간메모리
1300737gsalterKpart (eJOI21_kpart)C++20
100 / 100
1128 ms195992 KiB
#include "bits/stdc++.h"
using namespace std;

#define maxN 1005
#define maxS 50005
int a[maxN];
int prefix[maxS];
int dp[maxN][maxS];
int n;

void helper() {
    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);
    for (int i=1; i<=n; i++) prefix[i] = prefix[i-1] + a[i];
    
    for (int r=1; r<=n; r++) {
        for (int s=0; s<=maxS-5; s++) {
            dp[r][s] = dp[r-1][s];
            if (s==a[r]) dp[r][s] = r;
            if (s>a[r]) dp[r][s] = max(dp[r][s], dp[r-1][s-a[r]]);
        }
    }

    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 = prefix[r] - prefix[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--) helper();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...