oj.uz

Submission #248954

# Submission time Handle Problem Language Result Execution time Memory
248954 2020-07-13T18:44:06 Z JustasZ Olympiads (BOI19_olympiads) C++14
100 / 100
 71 ms 512 KB 
/*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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 432 KB Output is correct
2 Correct 8 ms 384 KB Output is correct
3 Correct 39 ms 384 KB Output is correct
4 Correct 27 ms 384 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 9 ms 384 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 8 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 19 ms 432 KB Output is correct
6 Correct 8 ms 384 KB Output is correct
7 Correct 39 ms 384 KB Output is correct
8 Correct 27 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 9 ms 384 KB Output is correct
12 Correct 7 ms 384 KB Output is correct
13 Correct 8 ms 384 KB Output is correct
14 Correct 6 ms 384 KB Output is correct
15 Correct 11 ms 512 KB Output is correct
16 Correct 24 ms 384 KB Output is correct
17 Correct 71 ms 504 KB Output is correct
18 Correct 28 ms 384 KB Output is correct
19 Correct 4 ms 512 KB Output is correct