Referência para TopCoder CollectingPostmarks (Luiza)

#include <math.h>
#include <time.h>
#include <string.h>
#include <stdio.h>

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

#define TRACE(x) x
#define PRINT(x) TRACE(printf(x))
#define WATCH(x) TRACE(cout << #x << " = " << x << endl;)

#define rep(i,n) for (int i=0; i<n; i++)

const int inf =0x3f3f3f3f;
const double eps = 1e-9;

pair<int,int> p1[(1<<16)+10];
pair<int,int> p2[(1<<16)+10];
int szP1, szP2;
vector<int> _prices;
vector<int> _values;
int _K;

int compute(int beg, int end, pair<int,int>* p) {
    int sz = end-beg;
    int cnt=0;

    for (int i=0; i<(1<<sz); i++) {
        int v=0,pr=0;

        for (int j=0; j<sz; j++)
            if (i&(1<<j)) {
                int idx=j+beg;
                pr+=_prices[idx];
                v+=_values[idx];
            }

        p[cnt++]=make_pair(v,pr);
    }

    sort(p,p+cnt);

    for (int i=0; i<cnt; i++)
        printf("%d, %d\n", p1[i].first, p1[i].second);

    return cnt;
}

int combine() {
    long long minMoney=INT_MAX;
    long long last=INT_MAX;

    int it2=szP2-1;
    for (int it1=0; it1<szP1; it1++) {
        while (it2>=0 && p1[it1].first+p2[it2].first>=_K)
            last = min(last, (long long)p2[it2--].second);
        minMoney=min(minMoney,last+p1[it1].second);
    }

    return (int)minMoney;
}

class CollectingPostmarks {
public:
   int amountOfMoney( vector <int> prices, vector <int> have, vector <int> values, int K ) {
    int sumValues=0;
    int n = prices.size();
    _K=K;
    _prices=prices;
    _values=values;

    for (int i=0; i<n; i++)
        sumValues+=values[i];
    if (sumValues<K) return -1;

    szP1 = compute(0,n/2,p1);
    szP2 = compute(n/2,n,p2);

    int need=combine();
    int moneyHave=0;

    for (int i=0; i<have.size(); i++)
        moneyHave+=prices[have[i]];

    return max(need-moneyHave,0);
   }
};