oj.uz

Submission #1106853

# Submission time Handle Problem Language Result Execution time Memory
1106853 2024-10-31T07:58:54 Z LucasLe Kpart (eJOI21_kpart) C++17
100 / 100
 1209 ms 952 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 336 KB Output is correct
2 Correct 16 ms 336 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 572 KB Output is correct
2 Correct 191 ms 592 KB Output is correct
3 Correct 201 ms 592 KB Output is correct
4 Correct 400 ms 760 KB Output is correct
5 Correct 857 ms 840 KB Output is correct
6 Correct 1209 ms 952 KB Output is correct
7 Correct 1087 ms 848 KB Output is correct