Submission #1078904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078904		Jawad_Akbar_JJ	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	368 ms	42648 KiB

tickets

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include "tickets.h"

using namespace std;
#define f first
#define s second

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

	if (m == 1){
		vector<int> vec;
		for (int i=0;i<n;i++)
			vec.push_back(x[i][0]), x[i][0] = 0;
		sort(begin(vec), end(vec));

		long long ans = 0;
		for (int i=0;i<n;i++)
			ans += abs(vec[n / 2] - vec[i]);
		allocate_tickets(x);
		return ans;
	}

	vector<pair<pair<int,int>,int>> vec;

	for (int i=0;i<n;i++){
		vec.push_back({{x[i][0], x[i][m-1]}, i});
		for (int j=0;j<m;j++)
			x[i][j] = -1;
	}

	sort(begin(vec), end(vec));
	multiset<pair<int,int>> ms;
	int h = n / 2;

	long long Mx = -1, ans = 0, ind = h - 1;
	for (int i=h-1;i<=n;i++){
		bool fl = false;
		if (i == n){
			i = ind;
			x[vec[i].s][0] = 0;
			fl = true;
		}
		int b = vec[i].f.f;
		ans = 0;
		ms.clear();

		for (int j=0;j<i;j++){
			ans += b - vec[j].f.f;
			if (vec[j].f.s >= b)
				ms.insert({vec[j].f.s - b - b + vec[j].f.f, vec[j].s});
			if (fl)
				x[vec[j].s][0] = 0;
		}
		int rem = h;
		for (int j=i+1;j<n;j++){
			ans += vec[j].f.s - b;
			if (fl)
				x[vec[j].s][m-1] = 0;
			rem--;
		}
		
		if (rem > ms.size())
			continue;
		
		while (rem--){
			auto [a, b] = *rbegin(ms);
			ans += a;
			if (fl){
				x[b][0] = -1;
				x[b][m-1] = 0;
			}
			ms.erase(prev(end(ms)));
		}
		if (fl)
			break;
		if (ans > Mx)
			Mx = ans, ind = i;
	}
	allocate_tickets(x);
	return Mx;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:67:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::multiset<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   if (rem > ms.size())
      |       ~~~~^~~~~~~~~~~

• 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