Submission #123006

#	Time	Username	Problem	Language	Result	Execution time	Memory
123006		model_code	Olympiads (BOI19_olympiads)	C++17	100 / 100	68 ms	1744 KiB

olympiads

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int N;
int C;
int scores[512][8];


class Shard {
public:
	int best[8];
	int score;
	
	vector<bool> forbidden;
	int numForced;
	
	Shard() {
		forbidden = vector<bool>(N);
		numForced = 0;
		eval();
	}
	Shard(Shard *source, int keep) {
		this->forbidden = source->forbidden;
		for (int i=0;i<keep;i++) {
			best[i] = source->best[i];
		}
		this->numForced = keep;
		forbidden[source->best[keep]] = true;
		eval();
	}
	
	void eval() {
		for (int i=numForced;i<C;i++) {
			int bestP = 0;
			int bestS = -100000000;
			
			for (int j=0;j<N;j++) {
				if (forbidden[j]) {
					continue;
				}
				if (cc(best, i, j)) {
					continue;
				}
				if (scores[j][i] > bestS) {
					bestS = scores[j][i];
					bestP = j;
				}
			}
			if (bestS < 0) {
				score = -1000000;
				return;
			}
			best[i] = bestP;
		}
		
		int score = 0;
		for (int i=0;i<C;i++) {
			int m = 0;
			for (int j=0;j<C;j++) {
				m = max(m, scores[best[j]][i]);
			}
			score += m;
		}
		this->score = score;
	}
	
	bool cc(int *best, int n, int v) {
		for (int i=0;i<n;i++) if (best[i]==v) return true;
		return false;
	}	
};

class ShardCmp {
public:
	bool operator() (Shard*a, Shard*b) {
		return a->score < b->score;
	}
};
priority_queue<Shard*, vector<Shard*>, ShardCmp> pq;


int ordinal(int player, int pos) {
	int g = 0;
	for (int j=0;j<N;j++)
		if (scores[j][pos] > scores[player][pos]) g++;
	return g;
}
int main() {
	int k;
	cin >> N >> C >> k;
	for (int i=0;i<N;i++)
		for (int j=0;j<C;j++)
			cin>>scores[i][j];
			
	pq.push(new Shard());
	
	int score = 0;

	Shard* f;	
	while (k) {
		f = pq.top();
		pq.pop();
//		cerr << "**** ";
//		for (int i=0;i<C;i++) cerr << f->best[i] << " ";
//		cerr << "Score of shard is " << f->score << endl;
		score = f->score;
		for (int i=f->numForced;i<C;i++) {
			Shard *n = new Shard(f, i);
			pq.push(n);
		}		
		k--;
	}
	cout << score << endl;
/*
	cerr << endl;
	for (int i=0;i<C;i++) {
		int p = f->best[i];
		printf("(");
		for (int j=0;j<C;j++) {
			if(j) printf(",");
			int tt = ordinal(p, j);
			printf("%4d", tt);
		}
		printf(")\n");
	}
*/
}

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