Submission #551332

#	Time	Username	Problem	Language	Result	Execution time	Memory
551332		valerikk	Olympiads (BOI19_olympiads)	C++17	100 / 100	21 ms	2252 KiB

olympiads

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 557;
const int K = 6;

int n, k, c;
int a[N][K];
int ord[K][N];
int pos[N][K];

bool better(int x, int y, int i) {
	return pos[x][i] < pos[y][i];
}

int nxt(int x, int i) {
	return pos[x][i] == n - 1 ? -1 : ord[i][pos[x][i] + 1];
}

int find_bad(const vector<int> &t) {
	for (int i = 0; i < k; ++i) {
		for (int j = 0; j < k; ++j) {
			if (better(t[j], t[i], i)) 
				return j;
		}
	}
	return -1;
}

int score(const vector<int> &t) {
	int res = 0;
	for (int i = 0; i < k; ++i) {
		res += a[t[i]][i];
	}
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> k >> c;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < k; ++j) {
			cin >> a[i][j];
		}
	}

	for (int i = 0; i < k; ++i) {
		iota(ord[i], ord[i] + n, 0);
		sort(ord[i], ord[i] + n, [&](int x, int y) {
			return make_pair(a[x][i], x) > make_pair(a[y][i], y);
		});
		for (int j = 0; j < n; ++j) {
			pos[ord[i][j]][i] = j;
		}
	}

	set<vector<int>> used;
	
	priority_queue<pair<int, vector<int>>, vector<pair<int, vector<int>>>> q;

	vector<int> st(k);
	for (int i = 0; i < k; ++i) {
		st[i] = ord[i][0];
	}

	used.insert(st);
	q.push({score(st), st});

	while (!q.empty()) {
		auto t = q.top().second;
		q.pop();

		for (int i = 0; i < k; ++i) {
			auto nt = t;
			nt[i] = nxt(nt[i], i);
			if (nt[i] == -1)
				continue;

			bool ok = true;
			// while (int j = find_bad(nt)) {
			// 	if (j == -1)
			// 		break;
			// 	nt[j] = nxt(nt[j], j);
			// 	if (nt[j] == -1) {
			// 		ok = false;
			// 		break;
			// 	} 
			// }

			if (ok && !used.count(nt)) {
				used.insert(nt);
				q.push({score(nt), nt});
			}
		}

		if (find_bad(t) != -1)
			continue;
		
		vector<int> diff;
		for (int i : t) {
			diff.push_back(i);
		}
		sort(diff.begin(), diff.end());
		diff.erase(unique(diff.begin(), diff.end()), diff.end());

		int need = k - (int)diff.size();

		int cnt = 0;

		for (int i = 0; i < n; ++i) {
			if (binary_search(diff.begin(), diff.end(), i)) 
				continue;

			bool ok = true;
			for (int j = 0; j < k; ++j) {
				if (better(i, t[j], j)) {
					ok = false;
					break;
				}
			}
			if (ok)
				++cnt;
		}

		if (need > cnt)
			continue;

		ll w = 1;
		for (int i = 1; i <= need; ++i) {
			w *= cnt - i + 1;
		}
		for (int i = 1; i <= need; ++i) {
			w /= i;
		}

		// cout << w << endl;

		while (w > 0 && c > 0) {
			--w;
			--c;
			
			if (c == 0) {
				cout << score(t) << endl;
				return 0;
			}
		}
	}

	return 0;
}

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