Submission #863736

#	Time	Username	Problem	Language	Result	Execution time	Memory
863736		NK_	Olympiads (BOI19_olympiads)	C++17	100 / 100	35 ms	11116 KiB

olympiads

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back
#define pf push_front
 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
 
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
 
using db = long double;
 
template<class T> using pq = priority_queue<T, V<T>, less<T>>;
 
const int MOD = 1e9 + 7;
const ll INFL = ll(1e17);
const ll BIG = ll(7e15);
const int LG = 18;
const int nax = 505;

int N, K, C;

struct Shard {
	int score; vi best, forced, forbitten;

	bool operator<(const Shard& a) const {
		return score < a.score;
	}	

	bool operator>(const Shard& a) const {
		return score > a.score;
	}	
};

int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N >> K >> C;

	V<vi> A(N, vi(K)); for(auto& v : A) {
		for(auto& x : v) cin >> x;
	}

	auto eval = [&](Shard s) -> Shard {
		vi best = {};
		vi ebest = vi(K, 0);
		vi used = vi(N, 0);

		for(auto& x : s.forced) {
			best.pb(x); used[x] = 1;
		}

		for(int i = sz(s.forced); i < K; i++) {
			best.pb(-1);
			for(int x = 0; x < N; x++) {
				if (!s.forbitten[x] && !used[x]) {
					if (best[i] == -1 || A[x][i] > A[best[i]][i]) {
						used[best[i]] = 0, used[x] = 1;
						best[i] = x;
					}
				}
			}
		}

		for(auto c : best) {
			if (c == -1) return Shard{-1, {}, {}, {}};
			for(int i = 0; i < K; i++) {
				ebest[i] = max(ebest[i], A[c][i]);
			}
		}

		return Shard{accumulate(begin(ebest), end(ebest), 0), best, s.forced, s.forbitten};
	};

	pq<Shard> q; q.push(eval(Shard{0, {}, {}, vi(N, 0)}));
	vi ans;

	while(sz(ans) < C) {
		Shard cur = q.top(); q.pop();

		ans.pb(cur.score);

		vi nforced = cur.forced;
		vi nforbitten = cur.forbitten;

		for(int i = sz(cur.forced); i < K; i++) {
			nforbitten[cur.best[i]] = 1;
			Shard ncur = eval({0, {}, nforced, nforbitten}); 
			if (ncur.score != -1) q.push(ncur);
			nforced.pb(cur.best[i]);
		}
	}

	cout << ans.back() << nl;


	exit(0-0);
} 	 

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