Submission #1150784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150784		vlqd0	Kpart (eJOI21_kpart)	C++20	0 / 100	2091 ms	120724 KiB

Main

#include <bits/stdc++.h>
using namespace std;

bool is_partition_possible(vector<int> v, int s){
    vector<int> possible_sums, to_add;
    possible_sums.push_back(0);
    possible_sums.push_back(v[0]);
    for (int i = 1; i < v.size(); i++){
        to_add = {};
        for (int j = 0; j < possible_sums.size(); j++){
            int current_sum = v[i] + possible_sums[j];
            if (current_sum == s) return true;
            to_add.push_back(current_sum);
        }
        for (int x : to_add) possible_sums.push_back(x);
    }
    return false;
}

void solve(){
    int n, current_num;
    vector<int> a;
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> current_num;
        a.push_back(current_num);
    }
    
    bool verdict;
    int sum_of_subvector;
    vector<int> subvector, done, ans_for_k;
    for (int k = 2; k <= n; k++){
        done = {};
        for (int i = 0; i < n; i++) done.push_back(0);
        for (int starting_index = 0; starting_index < (n - k + 1); starting_index++){
            
            if (starting_index == 0){
                subvector = {};
                sum_of_subvector = 0;
                for (int i = 0; i < k; i++) {subvector.push_back(a[i]); sum_of_subvector += a[i];}
            } else {
                sum_of_subvector -= subvector[0];
                sum_of_subvector += a[k + starting_index - 1];
                subvector.erase(subvector.begin());
                subvector.push_back(a[k + starting_index - 1]);
            }
            
            if (sum_of_subvector % 2) continue;
            if (is_partition_possible(subvector, (sum_of_subvector / 2))){
                for (int i = starting_index; i < (k + starting_index); i++) done[i] = 1;
            }
            
        }
        verdict = true;
        for (int b : done) if (b == 0) {verdict = false; break;} 
        if (verdict) ans_for_k.push_back(k);
    }
    
    cout << ans_for_k.size();
    for (int i : ans_for_k) cout << " " << i;
}

int main(){
    int t;
    cin >> t;
    while(t--) {solve(); cout << "\n";}

    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 70