Karuselli

#include <bits/stdc++.h>
 
#define ll long long 
#define pii pair<ll, ll>
#define pllk pair<long long, long long>
#define M 1000000007
#define INF 0x5ADFACE5
#define LINF 0x51DEEFFEC7C0DECALL
#define N (1<<17)
 
using namespace std;
 
pii v[14][N];
vector<pii> w[14];
int c[14];
int x[111111];
ll ans = 0;
ll s = 0;
int n, m;
 
void lol () {
	for (int i = 0; i < 10000; i++) {
		int a = rand() % n;
		int b = rand() % n;
		if (a == b) continue;
		int oa = c[a];
		int ob = c[b];
		s -= w[a][c[a]].first;
		s -= w[b][c[b]].first;
		x[w[a][c[a]].second]--;
		x[w[b][c[b]].second]--;
		
		s += w[a][ob].first;
		x[w[a][ob].second]++;
		int k = 0;
		while (x[w[b][k].second]) k++;
		s += w[b][k].first;
		x[w[b][k].second]++;
		
		if (s <= ans) {
			s -= w[a][ob].first;
			s -= w[b][k].first;
			s += w[a][oa].first;
			s += w[b][ob].first;
			x[w[a][c[a]].second]++;
			x[w[b][c[b]].second]++;
			x[w[a][ob].second]--;
			x[w[b][k].second]--;
		} else {
			c[a] = ob;
			c[b] = k;
			ans = s;
		}
	}
}
 
int main () {
	srand(time(0));
	cin>>n>>m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) cin>>v[i][j].first, v[i][j].second = j;
		sort(v[i], v[i] + m);
		reverse(v[i], v[i] + m);
		for (int j = 0; j < n; j++) w[i].push_back(v[i][j]);
	}
	if (n == 1) {
		cout<<v[0][0].first<<endl;
	} else if (false) {
		if (v[0][0].second == v[1][0].second) {
			cout<<max(v[0][0].first + v[1][1].first, v[0][1].first + v[1][0].first)<<endl;
		} else cout<<v[0][0].first + v[1][0].first<<endl;
	} else {
		int q[n];
		for (int i = 0; i < n; i++) {
			q[i] = i;
		}
		
		ll ma = 0;
		for (int i = 0; i < 25; i++) {
			random_shuffle(q, q + n);
			for (int i : q) x[w[i][c[i]].second]--;
			for (int i : q) {
				c[i] = 0;
				while (x[w[i][c[i]].second]) c[i]++;
				x[w[i][c[i]].second]++;
				s += w[i][c[i]].first;
			}
			ans = s;
			lol();
			ma = max(ans, ma);
		}
		cout<<ma<<endl;
	}
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: WRONG ANSWER

Test 3

Group: 1

Verdict: WRONG ANSWER

Test 4

Group: 1

Verdict: WRONG ANSWER

Test 5

Group: 1

Verdict: WRONG ANSWER

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: WRONG ANSWER

Test 8

Group: 2

Verdict: WRONG ANSWER

Test 9

Group: 2

Verdict: WRONG ANSWER

Test 10

Group: 2

Verdict: WRONG ANSWER

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: WRONG ANSWER

Test 14

Group: 3

Verdict: WRONG ANSWER

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED