Submission #1106853

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106853		LucasLe	Kpart (eJOI21_kpart)	C++17	100 / 100	1209 ms	952 KiB

Main

#include <bits/stdc++.h>

const int maxn = 1e5 + 5;

int n;
int a[maxn + 5];
int dp[maxn + 5];
bool ok[maxn + 5];

void solve() {
    std::cin >> n;
    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        std::cin >> a[i];
        sum += a[i];
    }
    for (int i = 1; i <= n; ++i) ok[i] = true;
    for (int i = 1; i <= sum; ++i) dp[i] = -1;
    for (int i = 1; i <= n; ++i) {
        for (int s = sum; s >= a[i]; --s) {
            if (s == a[i]) dp[s] = i;
            else dp[s] = std::max(dp[s], dp[s - a[i]]);
        }
        for (int j = i, cs = 0; j >= 1; --j) {
            cs += a[j];
            if ((cs & 1) || dp[cs / 2] < j) {
                ok[i - j + 1] = false;
                continue;
            }
        }
    }
    std::vector<int> res;
    for (int i = 1; i <= n; ++i) 
        if (ok[i]) res.push_back(i);
    std::cout << (int)res.size() << ' ';
    for (int x : res) std::cout << x << ' ';
    std::cout << '\n';
}  

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);

    // std::freopen("01-002.txt", "r", stdin);
    // std::freopen("output.txt", "w", stdout);

    int tc = 1;
    std::cin >> tc;
    while (tc--) solve();
}

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