fpSNha - Online C++0x Compiler & Debugging Tool

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

long long findClosestSumWithinCapacity(int n, const vector<long long>& requirements, long long processingCapacity) {
    int n1 = n / 2;
    int n2 = n - n1;

    vector<long long> sums1;
    for (int i = 0; i < (1 << n1); ++i) {
        long long current_sum = 0;
        for (int j = 0; j < n1; ++j) {
            if ((i >> j) & 1) {
                current_sum += requirements[j];
            }
        }
        sums1.push_back(current_sum);
    }

    vector<long long> sums2;
    for (int i = 0; i < (1 << n2); ++i) {
        long long current_sum = 0;
        for (int j = 0; j < n2; ++j) {
            if ((i >> j) & 1) {
                current_sum += requirements[n1 + j];
            }
        }
        sums2.push_back(current_sum);
    }

    sort(sums2.begin(), sums2.end());

    long long maxAchievable = 0;

    for (long long s1 : sums1) {
        long long remainingCapacity = processingCapacity - s1;
        if (remainingCapacity >= 0) {
            auto it = upper_bound(sums2.begin(), sums2.end(), remainingCapacity);
            if (it == sums2.begin()) {
                if (s1 <= processingCapacity) {
                    maxAchievable = max(maxAchievable, s1);
                }
            } else {
                maxAchievable = max(maxAchievable, s1 + *(--it));
            }
        } else {
            // If s1 itself is <= processingCapacity, consider it.
            if (s1 <= processingCapacity) {
                maxAchievable = max(maxAchievable, s1);
            }
        }
    }

    // Also consider sums only from the second half
    for (long long s2 : sums2) {
        if (s2 <= processingCapacity) {
            maxAchievable = max(maxAchievable, s2);
        }
    }

    return maxAchievable;
}

int main() {
    int n;
    cin >> n;

    vector<long long> requirements(n);
    for (int i = 0; i < n; ++i) {
        cin >> requirements[i];
    }

    long long processingCapacity;
    cin >> processingCapacity;

    long long result = findClosestSumWithinCapacity(n, requirements, processingCapacity);
    cout << result << endl;

    return 0;
}