Submission #133171

#	Time	Username	Problem	Language	Result	Execution time	Memory
133171		E869120	Olympiads (BOI19_olympiads)	C++14	44 / 100	2060 ms	13432 KiB

olympiads

#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 / 13
• Subtask 2: 31 / 31
• Subtask 3: 0 / 24
• Subtask 4: 0 / 32