oj.uz

Submission #863782

# Submission time Handle Problem Language Result Execution time Memory
863782 2023-10-21T03:39:09 Z Trisanu_Das Olympiads (BOI19_olympiads) C++17
100 / 100
 17 ms 1116 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int Z = 500, B = 6, MX = B * 1200;
int N, K, C, s[Z][B], a[MX][B], p[MX], cur;
bitset<Z> b[MX];
priority_queue<array<int, 2>> q;
 
void process() {
	int u = cur++, w[K] {};
	for(int j = K; j--; ) {
		if(a[u][j] < 0) {
			for(int i = N; i--; ) if(!b[u][i] && (a[u][j] < 0 || s[i][j] > s[a[u][j]][j])) a[u][j] = i;
			if(a[u][j] < 0) return;
			b[u][a[u][j]] = 1;
		}
		for(int i = K; i--; ) w[i] = max(w[i], s[a[u][j]][i]);
	}
	q.push({accumulate(w, w + K, 0), u});
}
 
int main() {
	cin >> N >> K >> C;
	for(int i = 0; i < N; ++i) for(int j = 0; j < K; ++j) cin >> s[i][j];
	fill(a[0], a[0] + K, -1);
	process();
	while(--C) {
		int u = q.top()[1]; q.pop();
		for(int j = K; --j >= p[u]; ) {
			b[cur] = b[u];
			p[cur] = j;
			b[u][a[u][j]] = 0;
			a[u][j] = -1;
			copy(a[u], a[u] + K, a[cur]);
			process();
		}
	}
	cout << q.top()[0];
}

Subtask #1
13.0 / 13.0

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

Subtask #2
31.0 / 31.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 856 KB Output is correct
2 Correct 10 ms 860 KB Output is correct
3 Correct 9 ms 860 KB Output is correct
4 Correct 9 ms 860 KB Output is correct
5 Correct 12 ms 1116 KB Output is correct
6 Correct 2 ms 856 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 7 ms 856 KB Output is correct
10 Correct 10 ms 860 KB Output is correct
11 Correct 9 ms 860 KB Output is correct
12 Correct 9 ms 860 KB Output is correct
13 Correct 12 ms 1116 KB Output is correct
14 Correct 2 ms 856 KB Output is correct
15 Correct 4 ms 604 KB Output is correct
16 Correct 12 ms 1040 KB Output is correct
17 Correct 17 ms 1116 KB Output is correct
18 Correct 7 ms 860 KB Output is correct
19 Correct 9 ms 900 KB Output is correct