Submission #248954

#	Time	Username	Problem	Language	Result	Execution time	Memory
248954		JustasZ	Olympiads (BOI19_olympiads)	C++14	100 / 100	71 ms	512 KiB

olympiads

/*input
5 4 4
7 0 4 9
3 0 8 4
1 1 3 7
5 1 3 4
4 2 2 9
*/
#include <bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define rd() abs((int)rng())
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
const int maxn = 2e5 + 100;
const int mod = 1e9 + 7;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int n, k, C, score[505][7], idx[505][7];
vector<pii>v[7];
vector<int>ppl;
int cnt = 0, negalima[505], need;
deque<int>ind[7];
void rec(int i) {
	if (cnt >= C) {
		return;
	}
 
	if (i == k) {
		cnt++;
		return;
	}
 
	for (int j = i; j < k; j++) {
		if (!sz(ind[j])) { // won't have any people to choose later
			return;
		}
	}
 
	stack<int>stk[k];
	vector<int>add_back;
	for (int j : ind[i]) {
		int cur = v[i][j].y;
		if (negalima[cur]) {
			continue;
		}
		
		ppl.pb(cur);
		negalima[cur] = 1;

		add_back.pb(cur);
 
		int cur_sum = 0;
		for (int ii = 0; ii <= i; ii++) {
			int mx = 0;
			for (int p : ppl) {
				mx = max(mx, score[p][ii]);
			}
			cur_sum += mx;
		}
 
		int max_sum = cur_sum;
		for (int ii = i + 1; ii < k; ii++) {
			int mx = 0;
			for (int p : ppl) {
				mx = max(mx, score[p][ii]);
			}
 
			while (sz(ind[ii]) > 0 && negalima[v[ii][ind[ii].front()].y]) {
				stk[ii].push(ind[ii].front());
				ind[ii].pop_front();
			}
 
			if (sz(ind[ii]) == 0) {
				ppl.pop_back();
				goto done;
			} else {
				mx = max(mx, v[ii][ind[ii].front()].x);
			}
			max_sum += mx;
		}
 
		if (max_sum >= need) {
			rec(i + 1);
		}
		ppl.pop_back();

		if (cnt >= C || max_sum < need) {
			break;
		}
	}
 
	done: ;
 
	for (int j = 0; j < k; j++) {
		while (sz(stk[j])) {
			ind[j].push_front(stk[j].top());
			stk[j].pop();
		}
	}
 
	while (sz(add_back) > 0) {
		int cur = add_back.back();
		add_back.pop_back();
		negalima[cur] = 0;
	}
}
void getcnt(int mid) {
	cnt = 0;
	need = mid;
	rec(0);
}
int main()
{
	ios_base::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++) {
			int a;
			cin >> a;
			score[i][j] = a;
			v[j].pb({a, i});
		}
	}
 
	for (int i = 0; i < k; i++) {
		sort(all(v[i]), greater<pii>());
		for (int j = 0; j < n; j++) {
			idx[v[i][j].y][i] = j;
		}
	}
 
	for (int i = 0; i < k; i++) {
		for (int j = 0; j < n; j++) {
			ind[i].pb(j);
		}
	}
 
 
	int l = 1, r = 6000010;
	while (l < r) {
		int mid = (l + r + 1) / 2;
 
		getcnt(mid);
 
		if (cnt < C) {
			r = mid - 1;
		} else {
			l = mid;
		}
	}
 
	cout << l << "\n";
	return 0;
}

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