Submission #500895

#	Time	Username	Problem	Language	Result	Execution time	Memory
500895		jesus_coconut	Olympiads (BOI19_olympiads)	C++17	100 / 100	86 ms	16924 KiB

olympiads

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define eb emplace_back();
#define all(a) begin(a), end(a)
using namespace std;

using ll = long long;
using pii = pair<int, int>;

int const N = 505;
int const K = 6;
int const C = 2005;
int n, k, c;
int a[N][K];

vector<array<int, N>> state;
vector<array<pair<int, bool>, K>> taken;

void load() {
	cin >> n >> k >> c;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < k; ++j) {
			cin >> a[i][j];
		}
	}
}

bool getBest(int p) {
	set<int> outs;
	for (int j = 0; j < k; ++j) {
		if (!taken[p][j].S) {
			taken[p][j].F = -1;
			outs.insert(-1);
			for (int i = 0; i < n; ++i) {
				if (state[p][i] == 0 && !outs.count(i)) {
					if (taken[p][j].F == -1 || a[taken[p][j].F][j] < a[i][j]) {
						outs.erase(taken[p][j].F);
						taken[p][j].F = i;
						outs.insert(i);
					}
				}
			}
			if (outs.count(-1)) return false;
		}
	}
	return true;
}

int getCost(int p) {
	int ret =0;
	for (int j = 0; j < k; ++j) {
		int cur = INT_MIN;
		for (int i = 0; i < k; ++i) {
			cur = max(cur, a[taken[p][i].F][j]);
		}
		ret += cur;
	}
	return ret;
}

void solve() {
	priority_queue<pii> pq;
	state.eb(0);
	taken.eb(0);
	getBest(0);
	pq.emplace(getCost(0), 0);
	int p = 0;
	for (int i = 1; i < c; ++i) {
		auto [cost, q] = pq.top();
		pq.pop();
		for (int j = 0; j < k; ++j) {
			if (!taken[q][j].S) {
				++p;
				state.eb(0);
				taken.eb(0);
				state.back() = state[q];
				taken.back() = taken[q];
				for (int l = 0; l < j; ++l) {
					if (!taken[q][l].S) {
						state.back()[taken[q][l].F] = 1;
						taken.back()[l].S = true;
					}
				}
				state.back()[taken[q][j].F] = -1;
				if (getBest(p)) {
					pq.emplace(getCost(p), p);
				}
			}
		}
	}
	cout << pq.top().F << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	load();
	solve();

	return 0;
}

Compilation message (stderr)

olympiads.cpp: In function 'void solve()':
olympiads.cpp:65:11: warning: statement has no effect [-Wunused-value]
   65 |  state.eb(0);
      |          ~^~
olympiads.cpp:66:11: warning: statement has no effect [-Wunused-value]
   66 |  taken.eb(0);
      |          ~^~
olympiads.cpp:76:14: warning: statement has no effect [-Wunused-value]
   76 |     state.eb(0);
      |             ~^~
olympiads.cpp:77:14: warning: statement has no effect [-Wunused-value]
   77 |     taken.eb(0);
      |             ~^~

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