Submission #715782

#	Time	Username	Problem	Language	Result	Execution time	Memory
715782		Ahmed57	Olympiads (BOI19_olympiads)	C++14	100 / 100	54 ms	10760 KiB

olympiads

#include <bits/stdc++.h>

using namespace std;
int k,n;
int p[501][7];
struct Partition{
    vector<int> best,choice;
    long long cost;
    Partition(vector<int> A):choice(A){
        vector<int> tmp(k,0);
        int cnt = 0;
        for(int i = 0;i<n;i++){
            if(choice[i]==1){
                cnt++;
                best.push_back(i);
                for(int j = 0;j<k;j++){
                    tmp[j] = max(tmp[j],p[i][j]);
                }
            }
        }
        vector<int> tt = choice;
        if(cnt>k){
            cost = INT_MIN;
            return ;
        }
        while(cnt<k){
            int mx = -1 , id = 0;
            for(int i = 0;i<n;i++){
                if(tt[i]==0&&mx<p[i][cnt]){
                    mx = p[i][cnt];
                    id = i;
                }
            }
            if(mx==-1){
                cost = INT_MIN;
                return ;
            }
            tt[id] = 1;
            best.push_back(id);
            for(int i = 0;i<k;i++){
                tmp[i] = max(tmp[i],p[id][i]);
            }
            cnt++;
        }
        cost = accumulate(tmp.begin(),tmp.end(),0);
    }
    bool operator <(Partition r) const{
		return cost < r.cost;
	}
};
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int c;cin>>n>>k>>c;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<k;j++){
            cin>>p[i][j];
        }
    }
    priority_queue<Partition> q;
    q.push(Partition(vector<int>(n, 0)));
    /*
    5 4 4
    7 0 4 9
    3 0 8 4
    1 1 3 7
    5 1 3 4
    4 2 2 9
    */
    while(c--){
        auto w = q.top();q.pop();
        if(c==0){
            cout<<w.cost<<"\n";
            return 0;
        }
        for(int i = 0;i<k;i++){
            if(w.choice[w.best[i]]==0){
                vector<int> choice = w.choice;
                choice[w.best[i]] = -1;
                for(int j = 0;j<i;j++){
                    choice[w.best[j]] = 1;
                }
                q.push(Partition(choice));
            }
        }
    }
}

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