oj.uz

Submission #1089342

# Submission time Handle Problem Language Result Execution time Memory
1089342 2024-09-16T10:15:58 Z vjudge1 Kpart (eJOI21_kpart) C++17
10 / 100
 2000 ms 1232 KB 
#include <bits/stdc++.h>
using namespace std;

int main(){

        // freopen("input.txt", "r", stdin);
        // freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;
    while(T--){
        int N;
        cin >> N;
        vector<int> A(N);
        for(auto &x: A) cin >> x;

        vector<long long> prefix_sum(N + 1, 0);
        for(int i = 0; i < N; i++) prefix_sum[i + 1] = prefix_sum[i] + A[i];

        vector<int> valid_K;
        for(int K = 1; K <= N; K++){
            bool all_even = true;
            const int MAX_SUM = 100000;
            vector<int> sum_to_window_start(MAX_SUM + 1, -1);
            for(int i = 0; i + K <= N; i++){
                long long S = prefix_sum[i + K] - prefix_sum[i];
                if(S > MAX_SUM){
                    all_even = false;
                    break;
                }
                if(S % 2 != 0){
                    all_even = false;
                    break;
                }
                if(sum_to_window_start[S] == -1){
                    sum_to_window_start[S] = i;
                }
            }
            if(!all_even){
                continue;
            }
            bool valid = true;
            for(int S = 0; S <= MAX_SUM; S++){
                if(sum_to_window_start[S] != -1){
                    int window_start = sum_to_window_start[S];
                    vector<int> window_elements(A.begin() + window_start, A.begin() + window_start + K);
                    int target = S / 2;
                    bitset<131072> bits;
                    bits.reset();
                    bits[0] = 1;
                    for(auto num: window_elements){
                        if(num > target){
                            continue; // Skip numbers greater than target
                        }
                        bits |= (bits << num);
                    }
                    if(!bits[target]){
                        valid = false;
                        break;
                    }
                }
            }
            if(valid){
                valid_K.push_back(K);
            }
        }

        // Output the result
        cout << valid_K.size();
        for(auto K: valid_K){
            cout << ' ' << K;
        }
        cout << '\n';
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 883 ms 1216 KB Output is correct
2 Execution timed out 2036 ms 1208 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

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