Submission #850870

#	Time	Username	Problem	Language	Result	Execution time	Memory
850870		serifefedartar	Olympiads (BOI19_olympiads)	C++17	100 / 100	30 ms	5144 KiB

olympiads

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 20;
const ll MAXN = 505;

vector<vector<int>> p;
int N, K, C;
struct Rule {
	vector<pair<int,int>> r;
	int res;

	Rule(vector<pair<int,int>> rl) {
		r = rl;
		res = 0;
		for (int i = 0; i < N; i++) {
			if (r[i].f == 2)
				r[i].f = 0;
		}

		set<int> taken;
		set<int> choice;
		for (int i = 0; i < N; i++) {
			if (r[i].f == 1) {
				taken.insert(i);
				choice.insert(r[i].s);
			}
		}

		for (int i = 0; i < K; i++) {
			if (choice.count(i) != 0)
				continue;

			int mx = 0;
			int mx_ind = -1;
			for (int j = 0; j < N; j++) {
				if (r[j].f == 0 && mx <= p[j][i]) {
					mx = p[j][i];
					mx_ind = j;
				}
			}
			if (mx_ind != -1) {
				taken.insert(mx_ind);
				r[mx_ind] = {2, i};
			}
		}

		if (taken.size() != K)
			res = -1;
		else {
			for (int i = 0; i < K; i++) {
				int mx_here = 0;
				for (auto u : taken)
					mx_here = max(mx_here, p[u][i]);
				res += mx_here;
			}
		}
	}
};

bool operator <(Rule A, Rule B) {
		return A.res < B.res;
}

int main() {
	fast
	cin >> N >> K >> C;

	p = vector<vector<int>>(N, vector<int>(K));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < K; j++)
			cin >> p[i][j];
	}

	priority_queue<Rule> pq;
	vector<pair<int,int>> emp(N, {0, -1});
	Rule new_rule = Rule(emp);
	pq.push(new_rule);

	while (true) {
		Rule now = pq.top();
		pq.pop();
		C--;

		if (C == 0) {
			cout << now.res << "\n";
			exit(0);
		}

		vector<pair<int,int>> R = now.r;
		for (int i = 0; i < N; i++) {
			if (R[i].f == 2) {
				R[i] = {-1, R[i].s};
				new_rule = Rule(R);
				if (new_rule.res != -1)
					pq.push(new_rule);
				R[i] = {1, R[i].s};
			}
		}
	}
}

Compilation message (stderr)

olympiads.cpp: In constructor 'Rule::Rule(std::vector<std::pair<int, int> >)':
olympiads.cpp:53:20: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |   if (taken.size() != K)
      |       ~~~~~~~~~~~~~^~~~

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