Submission #133278

#	Time	Username	Problem	Language	Result	Execution time	Memory
133278		square1001	Olympiads (BOI19_olympiads)	C++14	100 / 100	104 ms	4204 KiB

olympiads

#include <map>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N, K, C;
	cin >> N >> K >> C;
	vector<vector<int> > A(N, vector<int>(K));
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < K; ++j) {
			cin >> A[i][j];
		}
	}
	vector<vector<int> > perm(K, vector<int>(N));
	for (int i = 0; i < K; ++i) {
		for (int j = 0; j < N; ++j) {
			perm[i][j] = j;
		}
		sort(perm[i].begin(), perm[i].end(), [&](int j, int k) { return A[j][i] != A[k][i] ? A[j][i] > A[k][i] : j < k; });
	}
	map<vector<int>, bool> vis;
	priority_queue<pair<int, vector<int> > > que;
	int maxsum = 0;
	for (int i = 0; i < K; ++i) {
		maxsum += A[perm[i][0]][i];
	}
	que.push(make_pair(maxsum, vector<int>(K, 0)));
	long long cnt = 0;
	while (!que.empty()) {
		pair<int, vector<int> > bs = que.top(); que.pop();
		int score = bs.first;
		vector<int> v = bs.second;
		vector<bool> ban(N, false);
		vector<int> id(K);
		for (int i = 0; i < K; ++i) {
			id[i] = perm[i][v[i]];
			for (int j = 0; j < v[i]; ++j) {
				ban[perm[i][j]] = true;
			}
		}
		bool valid = true;
		for (int i = 0; i < K; ++i) {
			if (ban[id[i]]) valid = false;
		}
		if (valid) {
			sort(id.begin(), id.end());
			id.erase(unique(id.begin(), id.end()), id.end());
			int sel = -int(id.size());
			for (int i = 0; i < N; ++i) {
				if (!ban[i]) ++sel;
			}
			long long mul = 1;
			for (int i = 1; i <= K - id.size(); ++i) {
				mul *= sel - i + 1;
				mul /= i;
			}
			cnt += mul;
			if (cnt >= C) {
				cout << score << endl;
				break;
			}
		}
		for (int i = 0; i < K; ++i) {
			if (v[i] == N - 1) continue;
			vector<int> vnxt = v;
			++vnxt[i];
			if (vis[vnxt]) continue;
			int nxtscore = 0;
			for (int j = 0; j < K; ++j) {
				nxtscore += A[perm[j][vnxt[j]]][j];
			}
			vis[vnxt] = true;
			que.push(make_pair(nxtscore, vnxt));
		}
	}
	return 0;
}

Compilation message (stderr)

olympiads.cpp: In function 'int main()':
olympiads.cpp:57:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 1; i <= K - id.size(); ++i) {
                    ~~^~~~~~~~~~~~~~~~

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