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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Creditos a dmoj.ca
Codigo ejemplo ( ,, ):
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