Team with max efficiency

main.cpp

#include <vector>
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <exception>
#include <iterator>

typedef std::vector<size_t> TVector;

// max sum[v]
// v[0] + v[1] > v[last]
size_t max_team_eff(TVector& eff) {
    if (eff.empty()) {
        throw std::invalid_argument("empty input vector");
    }

    size_t n = eff.size();
    if (n < 3) {
        size_t max_eff = n == 1 ? eff[0] : eff[0] + eff[1];
        std::cout << max_eff << std::endl;
        return max_eff;
    }

    std::sort(eff.begin(), eff.end());
    TVector partial_sum;
    partial_sum.reserve(eff.size() + 1);
    partial_sum.push_back(0);
    size_t sum = 0;
    for (size_t x : eff) {
        sum += x;
        partial_sum.push_back(sum);
    }

    // 4 -> 3 + 2
    // 5 -> 3 + 3
    size_t max_eff = 0;
    const auto begin = eff.cbegin();
    for (size_t i = n; i--; ) {
        size_t eff_half_plus1 = 1 + (eff[i] >> 1);
        auto it = std::lower_bound(begin, begin + i, eff_half_plus1);
        if (it > begin && *(it - 1) + *it > eff[i]) {
            --it;
        }
        size_t team_eff = partial_sum[i + 1] - partial_sum[it - begin];
        if (max_eff < team_eff) max_eff = team_eff;
    }
    std::cout << max_eff << std::endl;
    return max_eff;
}

int main() {
    TVector v1{ 1 };
    max_team_eff(v1);

    TVector v2{ 1, 4 };
    max_team_eff(v2);

    TVector v3{ 1, 2, 4 };
    max_team_eff(v3);

    TVector v4{ 1, 1, 1, 1, 1, 1, 1 };
    max_team_eff(v4);

    TVector v5{ 1, 1, 1, 1, 1, 1, 7 };
    max_team_eff(v5);

    TVector v6{ 1, 1, 1, 1, 1, 1, 6 };
    max_team_eff(v6);

    TVector v7{ 1, 1, 1, 1, 1, 1, 5 };
    max_team_eff(v7);

    TVector v8{ 1, 1, 1, 1, 1, 1, 4 };
    max_team_eff(v8);

    TVector v9{ 4, 4, 2 };
    max_team_eff(v9);

    TVector v10{ 4, 3, 2 };
    max_team_eff(v10);

    TVector v11{ 4, 2, 2 };
    max_team_eff(v11);
    return 0;
}