Editorial for Island Evaluations

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

#include <iostream>
#include <set>
#include <vector>
#include <utility>
#include <algorithm>

int n, k;
int c, w;
std::vector< std::pair<int, int> > catalog;

int main() {
    std::cin >> n >> k;
    for(int i = 0; i < n; ++i) {
        std::cin >> c >> w;
        catalog.push_back(std::make_pair(w, c));
    }

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

    long long S = 0;
    long long costs = 0;
    std::set< std::pair<int, int> > items;

    for(int i = n - 1; i >= 0; --i){
        items.insert(std::make_pair(catalog[i].second, i));
        costs += catalog[i].second;
        while(items.size() > k){
            std::set< std::pair<int,int> >::iterator it = items.begin();
            costs -= it->first;
            items.erase(it);
        }
        S = std::max(S, costs * catalog[i].first);
    }

    if (S < 10000) 
        std::cout << "1 star" << std::endl;
    else if (S < 50000) 
        std::cout << "2 stars" << std::endl;
    else if (S < 1000000) 
        std::cout << "3 stars" << std::endl;
    else if (S < 5000000) 
        std::cout << "4 stars" << std::endl;
    else 
        std::cout << "5 stars" << std::endl;

    return 0;
}