Grupe X - 6.6.2 / pag 172

#include <bits/stdc++.h>

using namespace std;

const int v_max = 5e5 + 5;

bitset < v_max > sums;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N;
    cin >> N;
    vector < int > a(N);
    int sum = 0;
    for(int& x : a) {
        cin >> x;
        sum += x;
    }
    for(int x : a) {
        for(int i = 1; i <= sum; ++i)
            if(sums[i])
                sums[i + x] = true;
        sums[x] = true;
    }
    sum /= 2;
    int x = sum;
    while(!sums[x] && x > 0)
        --x;
    int y = sum;
    while(!sums[y])
        ++y;
    if(sum - x < y - sum)
        cout << sum - x;
    else
        cout << y - sum;
}