Submission #1089345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089345		vjudge1	Kpart (eJOI21_kpart)	C++17	0 / 100	2058 ms	528264 KiB

Main

#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 = 2; 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);
                    }
                    cout << bits << '\n';
                    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: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 70