Karuselli

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

int n;
int k;
const int N = 14;
const int K = 1e5;
std::pair<int, int> want[N][N];
bool used[K];
int done[N];

long long doit(int left) {
	long long max = 0;
	for (int i = 0; i < left; ++i) {
		int guy = done[i];
		done[i] = done[left - 1];
		int horse = 0;
		for (;; ++horse) {
			if (! used[want[guy][horse].second]) {
				break;
			}
		}
		used[want[guy][horse].second] = true;
		long long offer = doit(left - 1) + want[guy][horse].first; 
		if (offer > max) {
			max = offer;
		}
		done[left - 1] = done[i];
		done[i] = guy;
		used[want[guy][horse].second] = false;
	}
	return max;
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);

	std::cin >> n >> k;
	for (int i = 0; i < n; ++i) {
		std::vector<std::pair<int, int> > sort;
		for (int j = 0; j < k; ++j) {
			int v;
			std::cin >> v;
			sort.push_back(std::make_pair(-v, j));
		}
		std::sort(sort.begin(), sort.end());
		for (int j = 0; j < n; ++j) {
			want[i][j] = std::make_pair(-sort[j].first, sort[j].second);
		}
	}
	for (int i = 0; i < n; ++i) {
		done[i] = i;
	}
	std::cout << doit(n) << "\n";
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED