Submission #238674

#	Time	Username	Problem	Language	Result	Execution time	Memory
238674		grt	Olympiads (BOI19_olympiads)	C++17	100 / 100	58 ms	10772 KiB

olympiads

#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 500+10;
int n,k,c;
int score[nax][6];
bool selected[nax];

struct Team {
	int cost;
	vi taken;
	vi status;
	bool operator < (const Team &T) const {
		return cost < T.cost;
	}
};

Team find_best_team(vi arr) {
	Team ans;
	ans.cost = 0;
	ans.taken = {};
	ans.status = arr;
	for(int i = 0; i < n; ++i) {
		selected[i] = 0;
		if(arr[i] == 1) {
			ans.taken.PB(i);
			selected[i] = 1;
		}
	}
	for(int j = (int)ans.taken.size(); j < k; ++j) {
		pi mx = {-1,-1};
		for(int i = 0; i < n; ++i) {
			if(arr[i] == 0 && !selected[i]) {
				mx = max(mx, {score[i][j], i});
			}
		}
		if(mx.ST == -1) {
			ans.cost = -1;
			return ans;
		}
		ans.taken.PB(mx.ND);
		selected[mx.ND] = 1;
	}
	for(int i = 0; i < 6; ++i) {
		int mx = -1;
		for(int x : ans.taken) mx = max(mx,score[x][i]);
		ans.cost += mx;
	}
	return ans;
}

priority_queue<Team>q;

int solve() {
	vi em(n);
	for(int i = 0; i < n; ++i) em[i] = 0;
	q.push(find_best_team(em));
	while(!q.empty()) {
		Team tm = q.top();
		q.pop();
		//~ for(int x : tm.status) cout << x << " ";
		//~ cout << ": " << tm.cost << "\n";
		c--;
		if(c == 0) {
			return tm.cost;
		}
		vi arr = tm.status;
		for(int i = 0; i < k; ++i) {
			if(i > 0) {
				arr[tm.taken[i-1]] = 1;
			}
			if(arr[tm.taken[i]] == 1) continue;
			arr[tm.taken[i]] = -1;
			Team tmp = find_best_team(arr);
			if(tmp.cost != -1) {
				q.push(tmp);
			}
		}
	}
	return -1;
}

int main() {_
	cin >> n >> k >> c;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < k; ++j) {
			cin >> score[i][j];
		}
	}
	cout << solve();
}

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