Submission

Score: 0

User: nga12345

Problemset: ประลอง

Language: cpp

Time: 0.003 second

Submitted On: 2025-10-11 13:49:40

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <utility> 

using namespace std;

pair<vector<int>, vector<int>> findClosestSumPartitionArrays(const vector<int>& arr) {
    int total_sum = accumulate(arr.begin(), arr.end(), 0);
    int n = arr.size();
    if (n == 0) return {{}, {}};

    int target = total_sum / 2;

    vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));
    
    for (int i = 0; i <= n; ++i) {
        dp[i][0] = true;
    }

    for (int i = 1; i <= n; ++i) {
        int current_num = arr[i - 1]; 
        for (int j = 1; j <= target; ++j) {
            dp[i][j] = dp[i - 1][j];

            if (j >= current_num) {
                dp[i][j] = dp[i][j] || dp[i - 1][j - current_num];
            }
        }
    }

    int sum1 = 0;
    for (int j = target; j >= 0; --j) {
        if (dp[n][j]) {
            sum1 = j;
            break;
        }
    }

    vector<int> subset1;
    vector<int> subset2;
    int current_sum = sum1;
    vector<bool> in_subset1(n, false);
    
    for (int i = n; i >= 1; --i) {
        int num = arr[i - 1];
        
        if (dp[i - 1][current_sum]) {
            
        } else {
            subset1.push_back(num);
            current_sum -= num;
            in_subset1[i - 1] = true;
        }
    }

    for (int i = 0; i < n; ++i) {
        if (!in_subset1[i]) {
            subset2.push_back(arr[i]);
        }
    }
    
    reverse(subset1.begin(), subset1.end());
    sort(subset1.begin(), subset1.end());
    sort(subset2.begin(), subset2.end());

    return {subset1, subset2};
}

int main() {
    vector<int> a = {10, 4, 6, 3, 7, 9, 2};
    pair<vector<int>, vector<int>> result_a = findClosestSumPartitionArrays(a);

    for (size_t i = 0; i < result_a.first.size(); ++i) {
        cout << result_a.first[i] << " ";
    }

    cout << '\n';
    for (size_t i = 0; i < result_a.second.size(); ++i) {
        cout << result_a.second[i] << " ";
    }

    return 0;
}