Submission #661004

#	Time	Username	Problem	Language	Result	Execution time	Memory
661004		GusterGoose27	Olympiads (BOI19_olympiads)	C++11	37 / 100	3 ms	1688 KiB

olympiads

#include <bits/stdc++.h>

#define int long long

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 500;
int n, k, c;
int scores[MAXN][6];
int sort_pos[MAXN][6]; // what position in the array are you
pii sorted[6][MAXN];
ll choose[MAXN][6];

unordered_set<ll> vis;

class team {
public:
	int members[6]; // indices of members in array
	int num_below = 0;
	int score = 0;
	int num_distinct = 0;
	team() {
		fill(members, members+k, 0);
		num_below = n;
		for (int i = 0; i < k; i++) score += sorted[i][0].first;
		for (int i = 0; i < k; i++) {
			bool u = 1;
			for (int j = 0; j < i; j++) {
				if (sorted[i][0].second == sorted[j][0].second) {
					u = 0;
					break;
				}
			}
			num_distinct += u;
		}
	}
	void cpy(team &t) {
		for (int i = 0; i < k; i++) members[i] = t.members[i];
		num_below = t.num_below;
		score = t.score;
		num_distinct = t.num_distinct;
	}
	void get_same(int p, vector<int> &v) {
		for (int i = 0; i < k; i++)
			if (sorted[i][members[i]].second == sorted[p][members[p]].second)
				v.push_back(i);
	}
	bool valid(int v) {
		for (int i = 0; i < k; i++) {
			if (sort_pos[v][i] < members[i]) return 0;
		}
		return 1;
	}
	bool dist(int v) {
		for (int i = 0; i < k; i++) {
			if (i == v) continue;
			if (sorted[i][members[i]].second == sorted[v][members[v]].second) return 0;
		}
		return 1;
	}
	team(team &prv, int p) { // incrementing pos p
		cpy(prv);
		vector<int> s_vals;
		get_same(p, s_vals);
		num_distinct--;
		num_below--;
		for (int v: s_vals) {
			do {
				if (members[v] == n-1) {
					score = -1;
					return;
				}
				score -= sorted[v][members[v]].first;
				members[v]++;
			} while (!valid(sorted[v][members[v]].second));
			score += sorted[v][members[v]].first;
			num_distinct += dist(v);
		}
	}
	ll amt() {
		return choose[num_below-num_distinct][k-num_distinct];
	}
	ll get_hsh() {
		ll hsh = 0;
		for (int i = 0; i < k; i++) {
			hsh *= n;
			hsh += members[i];
		}
		return hsh;
	}
};

bool operator<(const team &a, const team &b) {
	return (a.score == b.score) ? (&a < &b) : (a.score < b.score);
}

priority_queue<team> pq;

void make_dupe(team &t) {
	for (int i = 0; i < k; i++) {
		pq.push(team(t, i));
	}
}

void make_options(int pos, int left, int best[], vector<int> &ops, int s = 0) {
	if (pos == n) {
		if (left) return;
		ops.push_back(s);
		return;
	}
	make_options(pos+1, left, best, ops, s);
	if (left == 0) return;
	int nbest[6];
	s = 0;
	for (int i = 0; i < k; i++) {
		nbest[i] = max(best[i], scores[pos][i]);
		s += nbest[i];
	}
	make_options(pos+1, left-1, nbest, ops, s);
}

int bash() {
	vector<int> options;
	int best[6];
	fill(best, best+k, 0);
	make_options(0, k, best, options);
	sort(options.begin(), options.end(), greater<int>());
	return options[c-1];
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> k >> c;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < k; j++) {
			if (j == 0) {
				choose[i][j] = 1;
				continue;
			}
			if (i == 0) {
				choose[i][j] = 0;
				continue;
			}
			choose[i][j] = choose[i-1][j]+choose[i-1][j-1];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < k; j++) {
			cin >> scores[i][j];
			sorted[j][i] = pii(scores[i][j], i);
		}
	}
	for (int i = 0; i < k; i++) sort(sorted[i], sorted[i]+n, greater<pii>());
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < k; j++) sort_pos[sorted[j][i].second][j] = i;
	}
	pq.push(team());
	// int b = bash();
	// cerr << b << endl;
	while (1) {
		team t = pq.top();
		pq.pop();
		ll hsh = t.get_hsh();
		if (vis.find(hsh) != vis.end()) continue;
		vis.insert(hsh);
		if (t.amt() >= c) {
			cout << t.score << "\n";
			// assert(t.score == b);
			return 0;
		}
		c -= t.amt();
		if (t.amt() > 0) make_dupe(t);
	}
}

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