Submission #1263455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263455		vvalsi	Kpart (eJOI21_kpart)	C++20	0 / 100	101 ms	580 KiB

Main

#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();
    }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 70