Submission #1079635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079635		anton	Olympiads (BOI19_olympiads)	C++17	100 / 100	77 ms	1380 KiB

olympiads

#include<bits/stdc++.h>

using namespace std;
#define int long long

const int MAX_N = 500, MAX_K= 6;
int N, K, C;
int level[MAX_N][MAX_K];
struct Constraints{
    vector<bool> alive = vector<bool>(N, true);
    vector<int> fixed;
    int nb_killed= 0;
    Constraints(){

    }
    pair<int, vector<int>> get_best_score(){
        int s= 0;
        vector<int> scores(K);
        vector<int> chosen;
        for(auto e: fixed){
            chosen.push_back(e);
        }
        while(chosen.size()<K){
            int dim =chosen.size();
            int best_score = -1;
            int best_player = 0;
            for(int i = 0; i<N; i++){
                if(alive[i] && count(chosen.begin(), chosen.end(), i) == 0){
                    if(level[i][dim]>best_score){
                        best_player = i;
                        best_score = level[i][dim];
                    }
                }
            }
            chosen.push_back(best_player);
        }

        for(auto e: chosen){
            for(int i  =0; i<K; i++){
                scores[i] = max(level[e][i], scores[i]);
            }
        }

        int res =0;
        for(auto e: scores){
            res += e;
        }
        return {res, chosen};
    }

    vector<Constraints> fracture(){
        vector<int> chosen = get_best_score().second;
        vector<Constraints> res;
        nb_killed++;
        if(N-nb_killed>=K){
            while(fixed.size()<K){
                int i = fixed.size();
                alive[chosen[i]] = false;
                res.push_back(*this);
                alive[chosen[i]] =true;
                fixed.push_back(chosen[i]);
            }
        }
        //cout<<"fracturing"<<endl;
        for(auto e: res){
            //cout<<e.get_best_score().first<<endl;
            for(auto ee: e.alive){
                //cout<<ee<<" ";
            }
            //cout<<endl;
            //cout<<"f ";
            for(auto ee: e.fixed){
                //cout<<ee<<" ";
            }
            //cout<<endl;
            //cout<<"c ";
            for(auto ee: e.get_best_score().second){
                //cout<<ee<<" ";
            }
            //cout<<endl;
        }
        //cout<<"done fract"<<endl;
        return res;
    }

    bool operator<(const Constraints& b)const{
        return false;
    }
};

signed main(){
    cin>>N>>K>>C;

    for(int i = 0; i<N; i++){
        for(int j = 0; j<K; j++){
            cin>>level[i][j];
        }
    }

    priority_queue<pair<int, Constraints>> pq;
    Constraints root = Constraints();
    pq.push({root.get_best_score().first, root});

    int rank =0;

    for(int i = 0; i<C; i++){
        auto cur = pq.top();
        pq.pop();
        for(auto e: cur.second.fracture()){
            pq.push({e.get_best_score().first, e});
        }
        if(i==C-1){
            cout<<cur.first<<endl;
        }
    }
    return 0;

}

Compilation message (stderr)

olympiads.cpp: In member function 'std::pair<long long int, std::vector<long long int> > Constraints::get_best_score()':
olympiads.cpp:23:28: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   23 |         while(chosen.size()<K){
      |               ~~~~~~~~~~~~~^~
olympiads.cpp:17:13: warning: unused variable 's' [-Wunused-variable]
   17 |         int s= 0;
      |             ^
olympiads.cpp: In member function 'std::vector<Constraints> Constraints::fracture()':
olympiads.cpp:56:31: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   56 |             while(fixed.size()<K){
      |                   ~~~~~~~~~~~~^~
olympiads.cpp:67:22: warning: variable 'ee' set but not used [-Wunused-but-set-variable]
   67 |             for(auto ee: e.alive){
      |                      ^~
olympiads.cpp:72:22: warning: unused variable 'ee' [-Wunused-variable]
   72 |             for(auto ee: e.fixed){
      |                      ^~
olympiads.cpp:77:22: warning: unused variable 'ee' [-Wunused-variable]
   77 |             for(auto ee: e.get_best_score().second){
      |                      ^~
olympiads.cpp: In function 'int main()':
olympiads.cpp:104:9: warning: unused variable 'rank' [-Wunused-variable]
  104 |     int rank =0;
      |         ^~~~

• Subtask 1: 13 / 13
• Subtask 2: 31 / 31
• Subtask 3: 24 / 24
• Subtask 4: 32 / 32