CSES - Leirikisa 6.3.2017 - Results
Submission details
Task:Karuselli
Sender:Kuha
Submission time:2017-03-06 18:57:39 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.13 s1details
#20.20 s1details
#30.17 s1details
#40.17 s1details
#50.20 s1details
#6ACCEPTED0.04 s2details
#70.07 s2details
#80.07 s2details
#90.06 s2details
#100.05 s2details
#11ACCEPTED0.10 s3details
#12--3details
#130.84 s3details
#140.85 s3details
#15--3details

Code

#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 details

Test 1

Group: 1

Verdict: ACCEPTED

input
1 100000
557222713 738086719 759310230 ...

correct output
999997412

user output
999997412

Test 2

Group: 1

Verdict:

input
2 100000
173028329 323213810 439376948 ...

correct output
1999979389

user output
49999393900

Test 3

Group: 1

Verdict:

input
2 100000
499570894 150469086 335977485 ...

correct output
1999973920

user output
49999240375

Test 4

Group: 1

Verdict:

input
2 100000
863032160 931625464 885185608 ...

correct output
1999939689

user output
49997930550

Test 5

Group: 1

Verdict:

input
2 100000
831463088 525853809 390350738 ...

correct output
1999969705

user output
49998724650

Test 6

Group: 2

Verdict: ACCEPTED

input
1 200
344318490 251860941 939326382 ...

correct output
998010019

user output
998010019

Test 7

Group: 2

Verdict:

input
14 200
43513423 154416018 137660602 1...

correct output
13918226615

user output
348443869418

Test 8

Group: 2

Verdict:

input
14 200
881307544 967733810 371467276 ...

correct output
13961979091

user output
348910446845

Test 9

Group: 2

Verdict:

input
14 200
522563563 350867137 498280483 ...

correct output
13912986556

user output
347733855143

Test 10

Group: 2

Verdict:

input
14 200
852825364 914968833 967854069 ...

correct output
13929235436

user output
347802955728

Test 11

Group: 3

Verdict: ACCEPTED

input
1 100000
157285470 474162109 440472842 ...

correct output
999998218

user output
999998218

Test 12

Group: 3

Verdict:

input
14 100000
971542960 589024445 443526352 ...

correct output
13999781843

user output
(empty)

Test 13

Group: 3

Verdict:

input
14 100000
255470528 36303969 757946964 7...

correct output
13999894454

user output
349992101725

Test 14

Group: 3

Verdict:

input
14 100000
18178744 935999032 93142616 43...

correct output
13999804193

user output
349992863425

Test 15

Group: 3

Verdict:

input
14 100000
316827351 638928258 809826490 ...

correct output
13999909014

user output
(empty)