oj.uz

답안 #1079635

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1079635 2024-08-28T19:34:34 Z anton Olympiads (BOI19_olympiads) C++17
100 / 100
 77 ms 1380 KB 
#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

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.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 8 ms 348 KB Output is correct
3 Correct 7 ms 448 KB Output is correct
4 Correct 6 ms 344 KB Output is correct

Subtask #2
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 480 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 9 ms 812 KB Output is correct
4 Correct 7 ms 744 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 472 KB Output is correct
2 Correct 12 ms 472 KB Output is correct
3 Correct 59 ms 1064 KB Output is correct
4 Correct 56 ms 888 KB Output is correct
5 Correct 22 ms 556 KB Output is correct
6 Correct 8 ms 676 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 8 ms 348 KB Output is correct
3 Correct 7 ms 448 KB Output is correct
4 Correct 6 ms 344 KB Output is correct
5 Correct 8 ms 480 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 9 ms 812 KB Output is correct
8 Correct 7 ms 744 KB Output is correct
9 Correct 16 ms 472 KB Output is correct
10 Correct 12 ms 472 KB Output is correct
11 Correct 59 ms 1064 KB Output is correct
12 Correct 56 ms 888 KB Output is correct
13 Correct 22 ms 556 KB Output is correct
14 Correct 8 ms 676 KB Output is correct
15 Correct 24 ms 600 KB Output is correct
16 Correct 40 ms 848 KB Output is correct
17 Correct 77 ms 1380 KB Output is correct
18 Correct 43 ms 856 KB Output is correct
19 Correct 12 ms 344 KB Output is correct