Submission #302544

#	Time	Username	Problem	Language	Result	Execution time	Memory
302544		circlethm	Carnival Tickets (IOI20_tickets)	C++17	11 / 100	2 ms	768 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pi;
typedef long long ll;

ll get_sum(vi elements, int b)
{
	ll total = 0;
	int n = elements.size();

	for (int i = 0; i < n; i++)
	{
		total += abs(b - elements[i]);
	}

	return total;
}

ll find_min_sum(vi elements, int max)
{

	const auto median_it = elements.begin() + elements.size() / 2;
	std::nth_element(elements.begin(), median_it, elements.end());
	auto median = *median_it;

	return get_sum(elements, median);
	// ll min_sum = 10E11;

	// int opt_b = 0;
	// for (int b = 0; b < max; b++)
	// {
	// 	ll sum = get_sum(elements, b);
	// 	// cout << "b: " << sum << endl;
	// 	if (sum < min_sum)
	// 	{
	// 		min_sum = sum;
	// 		opt_b = b;
	// 	}
	// }

	// return min_sum;
}

long long find_maximum(int k, std::vector<std::vector<int>> x)
{
	int n = x.size();

	vi elements;
	vector<vi> answer;
	int max = -1;

	for (int i = 0; i < n; i++)
	{
		vi row = {0};
		answer.push_back(row);
		int current_el = x[i][0];
		if (current_el > max)
			max = current_el;
		elements.push_back(current_el);
	}

	allocate_tickets(answer);
	return find_min_sum(elements, max);
}

• 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