Submission #301165

#	Time	Username	Problem	Language	Result	Execution time	Memory
301165		Khongor	Carnival Tickets (IOI20_tickets)	C++14	27 / 100	948 ms	51448 KiB

tickets

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

vector<vector<int>> ans;

// 1 5
// 10 10
// 8 12
// 12 20


long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	ans = vector<vector<int>>(n, vector<int>(m, -1));

	long long res = 0;
	for (int r = 0; r < k; r++) {
		vector<int> low(n), high(n);
		vector<pair<int, int>> a(n);
		for (int i = 0; i < n; i++) {
			int mn = -1;
			int mx = -1;
			for (int j = 0; j < m; j++)
				if (ans[i][j] == -1) {
					if (mn == -1 || x[i][j] < x[i][mn]) mn = j;
					if (mx == -1 || x[i][j] > x[i][mx]) mx = j;
				}
			low[i] = x[i][mn];
			high[i] = x[i][mx];
			a[i] = {mn, mx};
		}

		vector<int> best(n);
		long long bestDiff = -1;
		for (int md = 0; md < n; md++) {
			int median = low[md];
			vector<int> pick(n);
			int cntLow = 0, cntHigh = 0;
			vector<pair<int, int>> v;
			for (int i = 0; i < n; i++)
				if (high[i] <= median || i == md) { pick[i] = a[i].first; cntLow++; }
				else if (low[i] > median) { pick[i] = a[i].second; cntHigh++; }
				else {
					pick[i] = a[i].first;
					v.push_back({low[i] + high[i] - 2 * median, i});
				}
			if (cntHigh > n / 2) continue;
			if (cntLow > n / 2) continue;
			sort(v.rbegin(), v.rend());

			for (int i = 0; i < n / 2 - cntHigh; i++) {
				int j = v[i].second;
				pick[j] = a[j].second; 
			}

			long long diff = 0;
			vector<int> b(n);
			for (int i = 0; i < n; i++) b[i] = x[i][pick[i]];
			sort(b.begin(), b.end());
			for (int i = 0; i < n / 2; i++) diff += b[n - i - 1] - b[i];
			if (diff > bestDiff) {
				bestDiff = diff;
				best = pick;
			}
		}

		assert(bestDiff != -1);
		for (int i = 0; i < n; i++) ans[i][best[i]] = r;
		res += bestDiff;
	}

	allocate_tickets(ans);
	return res;
}

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