oj.uz

Submission #1025149

# Submission time Handle Problem Language Result Execution time Memory
1025149 2024-07-16T16:31:44 Z coolboy19521 Kpart (eJOI21_kpart) C++17
100 / 100
 1063 ms 1512 KB 
#include "bits/stdc++.h"
#define int long long

using namespace std;

const int sz = 1e3 + 3;
const int sm = 1e5 + 5;

bool r[sz];
int dp[sm];
int a[sz];

void solve() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i ++)
        cin >> a[i];

    fill_n(r, n + 1, true);
    fill_n(dp, sm, 0);

    for (int i = 1; i <= n; i ++) {
        for (int j = sm - 1; a[i] <= j; j --)
            dp[j] = max(dp[j], dp[j - a[i]]);
        dp[0] = dp[a[i]] = i;
        int sm = 0;
        for (int j = i; 1 <= j; j --) {
            sm += a[j];
            if (sm & 1 || dp[sm / 2] < j)
                r[i - j + 1] = false;
        }
    }

    vector<int> an;

    for (int i = 1; i <= n; i ++)
        if (r[i]) an.push_back(i);

    cout << an.size();
    for (int x : an)
        cout << ' ' << x;
    cout << '\n';
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int t;
    cin >> t;

    while (t --)
        solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1116 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 1116 KB Output is correct
2 Correct 119 ms 1112 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 1116 KB Output is correct
2 Correct 413 ms 1112 KB Output is correct
3 Correct 413 ms 1116 KB Output is correct
4 Correct 582 ms 1512 KB Output is correct
5 Correct 858 ms 1300 KB Output is correct
6 Correct 1063 ms 1256 KB Output is correct
7 Correct 992 ms 1324 KB Output is correct