oj.uz

Submission #697599

# Submission time Handle Problem Language Result Execution time Memory
697599 2023-02-10T14:00:13 Z Ooops_sorry Kpart (eJOI21_kpart) C++14
100 / 100
 763 ms 812 KB 
#include<bits/stdc++.h>

using namespace std;

#define ull unsigned long long
#define pb push_back
#define ld long double
#define ll long long
#define all(a) a.begin(), a.end()

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

const int N = 1010, M = 1e5 + 10;
int a[N], pr[N], mx[M];

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif // LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            pr[i] = pr[i - 1] + a[i];
            sum += a[i];
        }
        for (int i = 0; i <= sum; i++) {
            mx[i] = -1;
        }
        vector<int> good(n + 1, 1);
        for (int i = 1; i <= n; i++) {
            for (int j = sum / 2 - a[i]; j >= 0; j--) {
                mx[j + a[i]] = max(mx[j + a[i]], mx[j]);
            }
            mx[a[i]] = i;
            for (int j = i; j >= 1; j--) {
                if ((pr[i] - pr[j - 1]) & 1) {
                    good[i - j + 1] = 0;
                } else {
                    good[i - j + 1] &= j <= mx[(pr[i] - pr[j - 1]) / 2];
                }
            }
        }
        vector<int> ans;
        for (int i = 1; i <= n; i++) {
            if (good[i]) {
                ans.pb(i);
            }
        }
        cout << ans.size() << ' ';
        for (auto to : ans) cout << to << ' ';
        cout << endl;
    }
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 11 ms 340 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 456 KB Output is correct
2 Correct 106 ms 508 KB Output is correct
3 Correct 133 ms 592 KB Output is correct
4 Correct 236 ms 612 KB Output is correct
5 Correct 547 ms 768 KB Output is correct
6 Correct 763 ms 812 KB Output is correct
7 Correct 687 ms 780 KB Output is correct