Submission #623518

#	Time	Username	Problem	Language	Result	Execution time	Memory
623518		Jomnoi	Carnival Tickets (IOI20_tickets)	C++17	11 / 100	1 ms	596 KiB

tickets

#include <bits/stdc++.h>
#include "tickets.h"
using namespace std;

const int MAX_N = 1505;

int N, M, K, median;
long long ans;
int cnt[MAX_N], id[MAX_N];
int sz[MAX_N];

long long find_maximum(int k, vector <vector <int>> x) {
	N = x.size(), M = x[0].size(), K = k;
	vector <vector <int>> answer(N, vector <int> (M, -1));

	if(M == 1) {
		vector <int> vec;
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				answer[i][j] = 0;
				vec.push_back(x[i][j]);
			}
		}

		sort(vec.begin(), vec.end());

		median = vec[N / 2];
		for(int i = 0; i < N; i++) {
			ans += abs(median - vec[i]);
		}
	}
	else if(K == 1) {
		vector <int> vec;
		for(int i = 0; i < N; i++) {
			answer[i][M - 1] = 0;
			vec.push_back(x[i][M - 1]);
		}

		sort(vec.begin(), vec.end());

		median = vec[N / 2];
		for(int i = 0; i < N; i++) {
			ans += abs(median - vec[i]);
		}
	}
	else {
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				cnt[i] += x[i][j];
			}
		}

		iota(id, id + N, 0);
		sort(id, id + N, [&](const int &a, const int &b) {
			return cnt[a] < cnt[b];
		});

		for(int k = 0; k < K; k++) {
			vector <int> vec;
			for(int i = 0; i < N; i++) {
				if(id[i] < N / 2) {
					vec.push_back(x[i][sz[i]]);
					answer[i][sz[i]++] = k;
				}
				else {
					vec.push_back(x[i][M - sz[i] - 1]);
					answer[i][M - (sz[i]++) - 1] = k;
				}
			}

			sort(vec.begin(), vec.end());

			median = vec[N / 2];
			for(int i = 0; i < N; i++) {
				ans += abs(median - vec[i]);
			}
		}
	}

	allocate_tickets(answer);
	return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10