Amplitude Hackathon Winter '24 Problem 3 - Killer Queen

    1#include <bits/stdc++.h>
    2using namespace std;
    3using ll = long long;
    4using i128 = __int128;
    5const int inf = 1e9;
    6const ll INF = 2e18; //❄️
    7int main() {
    8    ios::sync_with_stdio(0); cin.tie(0); 
    9    vector<int> a(10), b(10);
    10    for (int i = 0; i < 20; i++) {
    11        if (i < 10) cin >> a[i];
    12        else cin >> b[i - 10];
    13    }
    14    ll ans = INF;
    15    vector<int> ta;
    16    vector<bool> ca(10);
    17    auto dfs = [&] (auto &&self, int pos, int cnt) -> void {
    18        if (cnt == 5) {
    19            vector<int> tb;
    20            for (int i = 0; i < 10; i++) {
    21                if (!ca[i]) tb.push_back(i);
    22            }
    23            ll pa = 0, pb = 0;
    24            for (int i = 0; i < ta.size(); i++) {
    25                pa += a[ta[i]];
    26            }
    27            for (int i = 0; i < tb.size(); i++) {
    28                pb += a[tb[i]];
    29            }
    30            for (int i = 0; i < ta.size(); i++) {
    31                ll na = pa - a[ta[i]] + b[ta[i]];
    32                for (int j = 0; j < tb.size(); j++) {
    33                    ll nb = pb - a[tb[j]] + b[tb[j]];
    34                    ans = min(ans, abs(na - nb));
    35                }
    36            }
    37            return;
    38        }
    39        if (pos == 10) return;
    40        ta.push_back(pos);
    41        ca[pos] = 1;
    42        self(self, pos + 1, cnt + 1);
    43        ta.pop_back();
    44        ca[pos] = 0;
    45        self(self, pos + 1, cnt);
    46    };
    47    dfs(dfs, 0, 0);
    48    cout << ans << '\n';
    49    return 0;
    50}