Submission #1079644

#TimeUsernameProblemLanguageResultExecution timeMemory
1079644oscar1fOlympiads (BOI19_olympiads)C++17
0 / 100
5 ms856 KiB
#include<bits/stdc++.h> using namespace std; #define int long long struct ensemble { int scoreMax; vector<int> listePris,listeObli,listeInterdit; //listePris doit être triée par nombre de meilleurs décroissant. bool operator < (const ensemble& autre) const { return scoreMax<autre.scoreMax; } }; const int MAX_CONCOURS=6,MAX_PERS=500+5; int nbPers,nbConcours,meilleur; int niv[MAX_PERS][MAX_CONCOURS]; vector<pair<int,int>> persTri[(1<<MAX_CONCOURS)]; priority_queue<ensemble> meilCour; ensemble vide; void ajout(ensemble ensCour) { /*for (int i:ensCour.listeObli) { cout<<i<<" "; } cout<<endl; for (int i:ensCour.listeInterdit) { cout<<i<<" "; } cout<<endl; cout<<endl;*/ if (nbPers-(int)ensCour.listeInterdit.size()<nbConcours) { return; } vector<bool> interdit(nbPers),obli(nbPers),pris(nbPers); vector<int> nbMeil(nbPers); for (int i:ensCour.listeInterdit) { interdit[i]=true; } set<int> ensPris; for (int i:ensCour.listeObli) { obli[i]=true; pris[i]=true; ensPris.insert(i); } //cout<<ensPris.size()<<endl; int posMeil=0,valMeil; ensCour.scoreMax=0; for (int i=0;i<nbConcours;i++) { valMeil=-1; for (int j=0;j<nbPers;j++) { if (!interdit[j] and (niv[j][i]>valMeil or (niv[j][i]==valMeil and obli[j]))) { valMeil=niv[j][i]; posMeil=j; } } //cout<<posMeil<<" "<<valMeil<<" "; ensCour.scoreMax+=valMeil; nbMeil[posMeil]++; pris[posMeil]=true; ensPris.insert(posMeil); } //cout<<ensPris.size()<<endl; assert((int)ensPris.size()<=nbConcours); set<int>::iterator it; for (int i=0;i<nbConcours;i++) { if (!interdit[i] and !pris[i] and (int)ensPris.size()<nbConcours) { pris[i]=true; ensPris.insert(i); } } ensCour.listePris.clear(); for (int i:ensPris) { ensCour.listePris.push_back(i); } sort(ensCour.listePris.begin(),ensCour.listePris.end(),[&] (int a,int b) { return nbMeil[a]<nbMeil[b]; }); meilCour.push(ensCour); } void decoupe(ensemble ensCour) { vector<bool> interdit(nbPers),obli(nbPers); for (int i:ensCour.listeInterdit) { interdit[i]=true; } for (int i:ensCour.listeObli) { obli[i]=true; } vector<int> listePossi; for (int i:ensCour.listePris) { if (!obli[i]) { listePossi.push_back(i); } } for (int i:listePossi) { ensCour.listeInterdit.push_back(i); ajout(ensCour); ensCour.listeInterdit.pop_back(); ensCour.listeObli.push_back(i); } } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>nbPers>>nbConcours>>meilleur; for (int i=0;i<nbPers;i++) { for (int j=0;j<nbConcours;j++) { cin>>niv[i][j]; } } ajout(vide); int dern=0; ensemble ensCours; for (int i=0;i<meilleur;i++) { ensCours=meilCour.top(); meilCour.pop(); dern=ensCours.scoreMax; decoupe(ensCours); } cout<<dern<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...