DGOLD - Chia vàng

Tác giả: RR

Ngôn ngữ: C++

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <vector>

#define FOR(i,a,b) for(int i=(a),_b=(b); i <= _b; ++i)
#define FORD(i,a,b) for(int i=(a),_b=(b); i >= _b; --i)
#define REP(i,a) for(int i=0,_a=(a); i < _a; ++i)
using namespace std;

int n, a[25], res;

struct HashTable {
    static const int HKEY = 1000003;
    vector< pair<int,int> > h[HKEY];

    inline int key(int s) const {
        int res = s % HKEY;
        if (res < 0) res += HKEY;
        return res;
    }

    void insert(int s, int val) {
        int k = key(s);
        REP(i,h[k].size())
        if (h[k][i].first == s) {
            h[k][i].second = max(h[k][i].second, val);
            return ;
        }
        h[k].push_back(make_pair(s, val));
    }

    int get(int s) {
        int k = key(s);
        REP(i,h[k].size()) {
            if (h[k][i].first == s)
                return h[k][i].second;
        }
        return -1000111000;
    }
} best;

void attempt1(int i, int r, int sum1, int sum2) {
    if (i > r) {
        best.insert(sum1 - sum2, sum1);
        return ;
    }

    attempt1(i+1, r, sum1, sum2);
    attempt1(i+1, r, sum1+a[i], sum2);
    attempt1(i+1, r, sum1, sum2+a[i]);
}

void attempt2(int i, int r, int sum1, int sum2) {
    if (i > r) {
        res = max(res, best.get(sum2-sum1) + sum1);
        return ;
    }

    attempt2(i+1, r, sum1, sum2);
    attempt2(i+1, r, sum1+a[i], sum2);
    attempt2(i+1, r, sum1, sum2+a[i]);
}

int main() {
    scanf("%d", &n); FOR(i,1,n) scanf("%d", &a[i]);
    int l1 = 1, r1 = n/2;
    int l2 = r1+1, r2 = n;

    attempt1(l1, r1, 0, 0);
    attempt2(l2, r2, 0, 0);
    cout << res << endl;
}

Download