Submission #697599

#	Time	Username	Problem	Language	Result	Execution time	Memory
697599		Ooops_sorry	Kpart (eJOI21_kpart)	C++14	100 / 100	763 ms	812 KiB

Main

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70