DGOLD - Chia vàng

Tác giả: ladpro98

Ngôn ngữ: C++

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define ii pair<int,int>
const int N = 25;
using namespace std;

pair<int, int> f[555555];
int a[N], n, lim, d, res;

int BS(int key) {
    int l = 1, r = d, k, m;
    while (l<=r) {
        m = (l+r) >> 1;
        if (f[m].first <= key) {
            k = m; l = m+1;
        }
        else r = m-1;
    }
    return k;
}

void Gen(int i, int x, int y) {
    if (i>lim) {
        d++;
        f[d].first = x-y;
        f[d].second = x;
        return;
    }
    Gen(i+1, x, y);
    Gen(i+1, x+a[i], y);
    Gen(i+1, x, y+a[i]);
}

void Back(int i, int x, int y) {
    if (i>n) {
        int t = BS(y-x);
        if (f[t].first==(y-x))
        res = max(res, f[t].second+x);
        return;
    }
    Back(i+1, x, y);
    Back(i+1, x+a[i], y);
    Back(i+1, x, y+a[i]);
}

int main()
{
    //freopen("DGOLD.in1","r",stdin);
    scanf("%d\n", &n);
    for(int i=1;i<=n;i++) scanf("%d\n", &a[i]);
    lim = n/2;
    Gen(1,0,0);
    sort(f+1, f+d+1);
    Back(lim+1,0,0);
    printf("%d", res);
    return 0;
}

Download