oj.uz

Submission #238406

# Submission time Handle Problem Language Result Execution time Memory
238406 2020-06-11T05:37:31 Z kshitij_sodani Olympiads (BOI19_olympiads) C++17
100 / 100
 80 ms 11024 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
int n,k,c;
int aa[501][6];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>k>>c;
	for(int i=0;i<n;i++){
		for(int j=0;j<k;j++){
			cin>>aa[i][j];
		}
	}
	priority_queue<pair<pair<int,vector<int>>,pair<vector<int>,vector<int>>>> ac;//score,sequence,fixed,forbidden index
	vector<int> bb;
	for(int i=0;i<k;i++){
		bb.pb(-1);
		for(int j=0;j<n;j++){
			int sto=0;
			for(auto ii:bb){
				if(ii==j){
					sto=1;
				}
			}
			if(sto==1){
				continue;
			}
			if(bb.back()==-1){
				bb.back()=j;
			}
			else if(aa[j][i]>aa[bb.back()][i]){
				bb.back()=j;
			}
		}
	}
		int score2=0;
		for(int m=0;m<k;m++){
			int ma=0;
			for(auto o:bb){
				ma=max(ma,aa[o][m]);
			}
			score2+=ma;
		}
		vector<int> ko;
		for(int i=0;i<n;i++){
			ko.pb(0);
		}
		ac.push({{score2,bb},{{},ko}});


	for(int ii=0;ii<c;ii++){
		pair<pair<int,vector<int>>,pair<vector<int>,vector<int>>> cc=ac.top();
		ac.pop();
	//	cout<<cc.a.a<<endl;
		if(ii==c-1){
			cout<<cc.a.a<<endl;
			return 0;
		}
		int xx=cc.b.a.size();
		for(int j=xx;j<k;j++){
			cc.b.b[cc.a.b[j]]=1;
			vector<int> best;
			for(int i=0;i<j;i++){
				best.pb(cc.a.b[i]);
			}
			int stt=0;
			for(int i=j;i<k;i++){
				best.pb(-1);
				for(int kk=0;kk<n;kk++){
					if(cc.b.b[kk]==0){
						int st=0;
						for(int jj=0;jj<best.size();jj++){
							if(best[jj]==kk){
								st=1;
							}
						}
						if(st==0){
							if(best.back()==-1){
								best.back()=kk;
							}
							else{
								if(aa[kk][i]>aa[best.back()][i]){
									best.back()=kk;
								}
							}
						}
					}
				}
			}
			for(int i=0;i<k;i++){
				if(best[i]==-1){
					stt=1;
				}
			}
			if(stt==0){
				int score=0;
				for(int m=0;m<k;m++){
					int ma=0;
					for(auto o:best){
						ma=max(ma,aa[o][m]);
					}
					score+=ma;
				}
				ac.push({{score,best},{cc.b.a,cc.b.b}});
			}

			cc.b.a.pb({cc.a.b[j]});
		}

	}

	return 0;
}

Compilation message

olympiads.cpp: In function 'int main()':
olympiads.cpp:79:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int jj=0;jj<best.size();jj++){
                    ~~^~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 512 KB Output is correct
2 Correct 13 ms 512 KB Output is correct
3 Correct 11 ms 512 KB Output is correct
4 Correct 10 ms 1280 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 768 KB Output is correct
2 Correct 7 ms 512 KB Output is correct
3 Correct 12 ms 1244 KB Output is correct
4 Correct 10 ms 896 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1664 KB Output is correct
2 Correct 36 ms 5572 KB Output is correct
3 Correct 52 ms 6988 KB Output is correct
4 Correct 46 ms 6100 KB Output is correct
5 Correct 19 ms 1792 KB Output is correct
6 Correct 8 ms 640 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 512 KB Output is correct
2 Correct 13 ms 512 KB Output is correct
3 Correct 11 ms 512 KB Output is correct
4 Correct 10 ms 1280 KB Output is correct
5 Correct 10 ms 768 KB Output is correct
6 Correct 7 ms 512 KB Output is correct
7 Correct 12 ms 1244 KB Output is correct
8 Correct 10 ms 896 KB Output is correct
9 Correct 21 ms 1664 KB Output is correct
10 Correct 36 ms 5572 KB Output is correct
11 Correct 52 ms 6988 KB Output is correct
12 Correct 46 ms 6100 KB Output is correct
13 Correct 19 ms 1792 KB Output is correct
14 Correct 8 ms 640 KB Output is correct
15 Correct 21 ms 1792 KB Output is correct
16 Correct 37 ms 5204 KB Output is correct
17 Correct 80 ms 11024 KB Output is correct
18 Correct 39 ms 4728 KB Output is correct
19 Correct 34 ms 5652 KB Output is correct