oj.uz

Submission #551334

# Submission time Handle Problem Language Result Execution time Memory
551334 2022-04-20T11:22:50 Z valerikk Olympiads (BOI19_olympiads) C++17
100 / 100
 27 ms 2096 KB 
#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();

		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;
			}
		}

		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 (true) {
				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});
			}
		}
	}

	return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 6 ms 484 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 8 ms 980 KB Output is correct
4 Correct 7 ms 1236 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 852 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 17 ms 1604 KB Output is correct
4 Correct 27 ms 1992 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 2 ms 468 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 6 ms 484 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 8 ms 980 KB Output is correct
8 Correct 7 ms 1236 KB Output is correct
9 Correct 7 ms 852 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 17 ms 1604 KB Output is correct
12 Correct 27 ms 1992 KB Output is correct
13 Correct 4 ms 596 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 21 ms 1104 KB Output is correct
16 Correct 5 ms 756 KB Output is correct
17 Correct 25 ms 2096 KB Output is correct
18 Correct 18 ms 1720 KB Output is correct
19 Correct 1 ms 340 KB Output is correct