Submission

Score: 60

User: chokun

Problemset: ประลอง

Language: cpp

Time: 0.004 second

Submitted On: 2026-10-14 19:35:22

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    
    vector<int> arr(n);
    int min_possible = 0;
    int max_possible = 0;
    int total_sum = 0;
    
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        total_sum += arr[i];
        if (arr[i] < 0) min_possible += arr[i];
        else max_possible += arr[i];
    }
    
    int target_k = n / 2;
    int offset = -min_possible;
    int S_range = max_possible - min_possible + 1;
    
    vector<vector<vector<bool>>> dp(n + 1, vector<vector<bool>>(target_k + 1, vector<bool>(S_range, false)));
    dp[0][0][offset] = true;
    
    for (int i = 0; i < n; i++) {
        int x = arr[i];
        for (int j = 0; j <= target_k; j++) {
            for (int s = 0; s < S_range; s++) {
                if (dp[i][j][s]) {
                    dp[i + 1][j][s] = true;
                    
                    if (j + 1 <= target_k && s + x >= 0 && s + x < S_range) {
                        dp[i + 1][j + 1][s + x] = true;
                    }
                }
            }
        }
    }
    
    int best_diff = 2e9;
    int best_sum_idx = offset;
    for (int s = 0; s < S_range; s++) {
        if (dp[n][target_k][s]) {
            int actual_sum = s - offset;
            int diff = abs(2 * actual_sum - total_sum);
            if (diff < best_diff) {
                best_diff = diff;
                best_sum_idx = s;
            }
        }
    }
    
    int curr_j = target_k;
    int curr_s = best_sum_idx;
    vector<bool> in_team1(n, false);
    
    for (int i = n - 1; i >= 0; i--) {
        int x = arr[i];
        bool can_take = false;
        
        if (curr_j > 0 && curr_s - x >= 0 && curr_s - x < S_range) {
            if (dp[i][curr_j - 1][curr_s - x]) {
                can_take = true;
            }
        }
        
        if (can_take) {
            in_team1[i] = true;
            curr_j--;
            curr_s -= x;
        } else {
            in_team1[i] = false;
        }
    }
    
    bool first = true;
    for (int i = 0; i < n; i++) {
        if (in_team1[i]) {
            if (!first) cout << " ";
            cout << arr[i];
            first = false;
        }
    }
    cout << "\n";
    
    first = true;
    for (int i = 0; i < n; i++) {
        if (!in_team1[i]) {
            if (!first) cout << " ";
            cout << arr[i];
            first = false;
        }
    }
    cout << "\n";
}