oj.uz

Submission #912583

# Submission time Handle Problem Language Result Execution time Memory
912583 2024-01-19T16:01:41 Z andro Kpart (eJOI21_kpart) C++14
0 / 100
 2000 ms 848 KB 
#include <bits/stdc++.h>

#define int long long

#define double long double

using namespace std;

const int N = 1e6;

bitset<N> dp;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while(t-- ) {
        int n;
        cin >> n;
        vector<int> a(n + 1);
        for(int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        vector<int> ans;
        vector<int> pref(n + 1);
        for(int i = 1; i <= n; i++) {
            pref[i] = pref[i - 1] + a[i];
        }
        for(int k = 1; k <= n; k++) {
            dp[0] = 1;
            for(int i = 1; i <= k; i++) {
                dp |= (dp << a[i]);
            }
            if(pref[k] % 2) {
                continue;
            }
            if(! dp[(pref[k]) / 2]) {
                continue;
            }
            int ok = 1;
            for(int i = k + 1; i <= n; i++) {
                dp |= (dp >> a[i - k]);
                dp[0] = 1;
                dp |= (dp << a[i]);
                if((pref[i] - pref[i - k]) % 2) {
                    ok = 0;
                    break;
                }
                if(! dp[(pref[i] - pref[i - k]) / 2]) {
                    ok = 0;
                    break;
                }
            }
            for(int i = 1; i <= n; i++) {
                dp |= (dp >> a[i]);
            }
            if(ok) {
                ans.push_back(k);
            }
        }
        cout << ans.size() << " ";
        for(auto it : ans) {
            cout << it << " ";
        }
        cout << "\n";
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 299 ms 796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2019 ms 796 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2021 ms 848 KB Time limit exceeded
2 Halted 0 ms 0 KB -