Editorial for Olympiads


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.

Author: Marco_Escandon

Creditos a dmoj.ca

Codigo ejemplo ( Daniel_1997,Diego_09, Maite_Morales):

int n,k,c;
cin >> n >> k >> c;

vector<vector<int> >player(n + 1,vector<int>(k + 1));

for(int i = 1; i <= n; i++)
{
    for(int j = 1; j <= k; j++)
    {
        cin >> player[i][j];
    }
}

int points = 0;
vector<string>used(n + 1,"Maybe");

for(int j = 1; j <= k; j++)
{
    int  best = 0;
    pair<int,int>best0 = {0,-1};
    for(int i = 1; i <= n; i++)
    {
        if(used[i] == "Now on the team")continue;
        if(used[i] == "Maybe")best0 = max(best0,{player[i][j],i});
        best = max(best,player[i][j]);
    }

    points += best;
    used[best0.sc] = "Now on the team";

}

priority_queue<pair<int,vector<string> > >q;
q.push({points,used});


while(c--) {
    auto[points,used] = q.top();q.pop();
    vector<string>new_used = used;

    if(c == 0) {
        cout << points << endl;
        return;
    }

    for(int i = 1; i <= n; i++)
    {
        if(new_used[i] == "Now on the team")new_used[i] = "Maybe";
    }

    for(int h = 1; h <= n; h++)
    {
        if(used[h] == "Now on the team") {
            new_used[h] = "Forbidden";

            int new_points = 0;
            vector<string>best_team(n + 1,"Maybe");


            for(int j = 1; j <= k; j++)
            {
                int  best = 0;
                pair<int,int>best0 = {0,-1};
                for(int i = 1; i <= n; i++)
                {
                    if(new_used[i] == "Forbidden")continue;
                    if(best_team[i] == "Maybe")best0 = max(best0,{player[i][j],i});
                    best = max(best,player[i][j]);
                }


                new_points += best;
                if(best0.sc != -1)best_team[best0.sc] = "Now on the team";
                else {
                    new_points = -1;
                    break;
                }
            }

            if(new_points != -1) {
                for(int i = 1; i <= n; i++) {
                    if(new_used[i] == "Mandatory" || new_used[i] == "Forbidden")best_team[i] = new_used[i];
                }

                q.push({new_points,best_team});
            }


            new_used[h] = "Mandatory";
        }
    }
}

Comments

There are no comments at the moment.