Football Team

#include <iostream>
#include <iterator>
#include <random>
#include <vector>

struct Player {
    Player(uint32_t number, uint32_t efficiency) : number(number), efficiency(efficiency) {
    }

    uint32_t number;
    uint32_t efficiency;
};

bool CompareByNumber(const Player& lhs, const Player& rhs) {
    return lhs.number < rhs.number;
}

bool CompareByEfficiency(const Player& lhs, const Player& rhs) {
    return lhs.efficiency < rhs.efficiency;
}

template <class Iter, class Compare>
Iter Partition(Iter left, Iter right, Iter pivot, Compare comp) {
    std::iter_swap(pivot, left);
    pivot = left;

    while (left < right) {
        do {
            ++left;
        } while ((left < right) && comp(*left, *pivot));

        do {
            --right;
        } while (comp(*pivot, *right));

        if (left < right) {
            std::iter_swap(left, right);
        }
    }

    std::iter_swap(pivot, std::prev(left));
    return left;
}

template <class Iter, class Compare, class Generator>
void QuickSort(Iter first, Iter last, Compare comp, Generator& generator) {
    while (std::distance(first, last) > 1) {
        std::uniform_int_distribution<int> random_step(0, std::distance(first, last) - 1);
        Iter pivot = std::next(first, random_step(generator));
        Iter partition = Partition(first, last, pivot, comp);
        if (std::distance(first, partition) < std::distance(partition, last)) {
            QuickSort(first, partition, comp, generator);
            first = partition;
        } else {
            QuickSort(partition, last, comp, generator);
            last = partition;
        }
    }
}

template <class Iter, class Compare>
void Sort(Iter first, Iter last, Compare comp) {
    std::mt19937 generator(42);
    QuickSort(first, last, comp, generator);
}

std::vector<Player> ReadPlayers() {
    int count;
    std::cin >> count;

    std::vector<Player> players;
    players.reserve(count);

    for (int i = 1; i <= count; ++i) {
        uint32_t efficiency;
        std::cin >> efficiency;
        players.emplace_back(i, efficiency);
    }

    return players;
}

uint64_t CountTeamEfficiency(std::vector<Player>::iterator first,
                            std::vector<Player>::iterator last) {
    uint64_t team_efficiency = 0;

    for (auto it = first; it < last; ++it) {
        team_efficiency += it->efficiency;
    }

    return team_efficiency;
}

struct Team {
    Team(std::vector<Player>::iterator first, std::vector<Player>::iterator last)
        : efficiency(CountTeamEfficiency(first, last)), first(first), last(last) {
    }

    uint64_t efficiency;
    std::vector<Player>::iterator first;
    std::vector<Player>::iterator last;
};

std::vector<Player> BuildMostEffectiveSolidaryTeam(std::vector<Player> players) {
    if (players.size() < 3) {
        return players;
    }

    Sort(players.begin(), players.end(), CompareByEfficiency);

    Team team(players.begin(), std::next(players.begin(), 2));
    Team best_team = team;

    while (team.last != players.end()) {
        uint64_t efficiency_of_two_weakest =
            static_cast<uint64_t>(team.first->efficiency) + std::next(team.first)->efficiency;

        while ((team.last != players.end()) &&
               (team.last->efficiency <= efficiency_of_two_weakest)) {

            team.efficiency += team.last->efficiency;
            ++team.last;
        }

        if (team.efficiency > best_team.efficiency) {
            best_team = team;
        }

        team.efficiency -= team.first->efficiency;
        ++team.first;
    }

    return {best_team.first, best_team.last};
}

void WriteTeam(std::vector<Player> team) {
    Sort(team.begin(), team.end(), CompareByNumber);

    uint64_t team_efficiency = CountTeamEfficiency(team.begin(), team.end());
    std::cout << team_efficiency << '\n';

    for (const Player& player : team) {
        std::cout << player.number << ' ';
    }

    std::cout << '\n';
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::vector<Player> players = ReadPlayers();
    std::vector<Player> team = BuildMostEffectiveSolidaryTeam(players);
    WriteTeam(team);
}