oj.uz

Submission #133171

# Submission time Handle Problem Language Result Execution time Memory
133171 2019-07-20T08:28:11 Z E869120 Olympiads (BOI19_olympiads) C++14
44 / 100
 2000 ms 13432 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long N, K, P, C[509][6], D[509], A[6000009];

int main() {
	cin >> N >> K >> P;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < K; j++) cin >> C[i][j];
	}
	if (K == 1) {
		for (int i = 0; i < N; i++) A[C[i][0]]++;
	}
	if (K == 2) {
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) A[max(C[i][0], C[j][0]) + max(C[i][1], C[j][1])]++;
		}
	}
	if (K == 3) {
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				for (int r = 0; r < K; r++) D[r] = 0;
				for (int r = 0; r < K; r++) D[r] = max(D[r], C[i][r]);
				for (int r = 0; r < K; r++) D[r] = max(D[r], C[j][r]);

				for (int k = j + 1; k < N; k++) {
					long long s = 0;
					for (int r = 0; r < K; r++) s += max(D[r], C[k][r]);
					A[s]++;
				}
			}
		}
	}
	if (K == 4) {
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				for (int k = j + 1; k < N; k++) {
					for (int r = 0; r < K; r++) D[r] = 0;
					for (int r = 0; r < K; r++) D[r] = max(D[r], C[i][r]);
					for (int r = 0; r < K; r++) D[r] = max(D[r], C[j][r]);
					for (int r = 0; r < K; r++) D[r] = max(D[r], C[k][r]);

					for (int l = k + 1; l < N; l++) {
						long long s = 0;
						for (int r = 0; r < K; r++) s += max(D[r], C[l][r]);
						A[s]++;
					}
				}
			}
		}
	}
	if (K == 5) {
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				for (int k = j + 1; k < N; k++) {
					for (int l = k + 1; l < N; l++) {
						for (int r = 0; r < K; r++) D[r] = 0;
						for (int r = 0; r < K; r++) D[r] = max(D[r], C[i][r]);
						for (int r = 0; r < K; r++) D[r] = max(D[r], C[j][r]);
						for (int r = 0; r < K; r++) D[r] = max(D[r], C[k][r]);
						for (int r = 0; r < K; r++) D[r] = max(D[r], C[l][r]);

						for (int m = l + 1; m < N; m++) {
							long long s = 0;
							for (int r = 0; r < K; r++) s += max(D[r], C[m][r]);
							A[s]++;
						}
					}
				}
			}
		}
	}
	if (K == 6) {
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				for (int k = j + 1; k < N; k++) {
					for (int l = k + 1; l < N; l++) {
						for (int m = l + 1; m < N; m++) {
							for (int r = 0; r < K; r++) D[r] = 0;
							for (int r = 0; r < K; r++) D[r] = max(D[r], C[i][r]);
							for (int r = 0; r < K; r++) D[r] = max(D[r], C[j][r]);
							for (int r = 0; r < K; r++) D[r] = max(D[r], C[k][r]);
							for (int r = 0; r < K; r++) D[r] = max(D[r], C[l][r]);
							for (int r = 0; r < K; r++) D[r] = max(D[r], C[m][r]);

							for (int n = m + 1; n < N; n++) {
								long long s = 0;
								for (int r = 0; r < K; r++) s += max(D[r], C[n][r]);
								A[s]++;
							}
						}
					}
				}
			}
		}
	}

	long long s = 0;
	for (int i = 6000000; i >= 0; i--) {
		s += A[i];
		if (s >= P) {
			cout << i << endl;
			break;
		}
	}
	return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 13432 KB Output is correct
2 Correct 20 ms 376 KB Output is correct
3 Correct 20 ms 376 KB Output is correct
4 Correct 15 ms 376 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 7772 KB Output is correct
2 Correct 72 ms 8540 KB Output is correct
3 Correct 83 ms 9340 KB Output is correct
4 Correct 80 ms 10100 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2060 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 13432 KB Output is correct
2 Correct 20 ms 376 KB Output is correct
3 Correct 20 ms 376 KB Output is correct
4 Correct 15 ms 376 KB Output is correct
5 Correct 77 ms 7772 KB Output is correct
6 Correct 72 ms 8540 KB Output is correct
7 Correct 83 ms 9340 KB Output is correct
8 Correct 80 ms 10100 KB Output is correct
9 Execution timed out 2060 ms 376 KB Time limit exceeded
10 Halted 0 ms 0 KB -