제출 #1263455

#제출 시각아이디문제언어결과실행 시간메모리
1263455vvalsiKpart (eJOI21_kpart)C++20
0 / 100
101 ms580 KiB
#include <bits/stdc++.h>
using namespace std;
void solve() {
    const int C = 50001;
    int n; cin >> n;
    vector<int> dp(C, -1); dp[0] = -1;
    vector<int> k(n - 1);
    iota(k.begin(), k.end(), 2);
    vector<int> a(n), pr(n + 1);
    for (int i = 0; i < n; i++) { cin >> a[i]; pr[i+1]=pr[i]+a[i]; }
    auto sum = [&](int l, int r) {return pr[r + 1] - pr[l]; };
    if (a[0] < C) dp[a[0]] = 0;
    for (int i = 1; i < n; i++) {
        for (int x = 0; x + a[i] < C; x++) {
            dp[x + a[i]] = max(dp[x + a[i]], dp[x]);
        }
        if (a[i] < C) dp[a[i]] = i;
        vector<int> now; //cout << ":: ";
        for (int x : k) {
            int j = i - x + 1;
            if (j < 0) {now.push_back(x); continue;}
            int s = sum(j, i);
            if (s % 2 == 0 && dp[s / 2] >= j) now.push_back(x);
            //cout << x  << ' ';
        }
        k = now; //cout << endl;
    }
    cout << (int)k.size() << endl; for (int x : k) cout << x << ' '; cout << endl;
}
int main() {
    int test; cin>>test; while (test--){
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...