Submission #541896

#	Time	Username	Problem	Language	Result	Execution time	Memory
541896		LucaDantas	Carnival Tickets (IOI20_tickets)	C++17	41 / 100	816 ms	88676 KiB

tickets

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

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

	if(k == 1) {
		long long ans = 0;
		vector<vector<int>> build(n, vector<int>(m, -1));

		for(int i = 0; i < n; i++)
			ans -= x[i][0], build[i][0] = 0;

		vector<pair<int,int>> opt;
		for(int i = 0; i < n; i++)
			opt.push_back({x[i].back() + x[i].front(), i});
		sort(opt.begin(), opt.end(), greater<pair<int,int>>());
		
		for(int i = 0; i < n/2; i++)
			build[opt[i].second].front() = -1, build[opt[i].second].back() = 0, ans += opt[i].first;

		allocate_tickets(build);
		return ans;
	}

	if(k == m) {
		long long ans = 0;
		vector<pair<int,pair<int,int>>> all;
		vector<vector<int>> build(n, vector<int>(m, -1));

		for(int i = 0; i < n; i++)
			for(int j = 0; j < m; j++)
				all.push_back({x[i][j], {i, j}});
		sort(all.begin(), all.end());
		
		vector<vector<int>> rm(n), add(n);
		
		for(int i = 0; i < n*m/2; i++)
			rm[all[i].second.first].push_back(all[i].second.second), ans -= all[i].first;
		
		for(int i = n*m/2; i < n*m; i++)
			add[all[i].second.first].push_back(all[i].second.second), ans += all[i].first;
		
		vector<vector<bool>> mark(n, vector<bool>(m));
		int index = 0;
		for(int i = 0; i < n; i++)
			for(int j = 0; j < (int)rm[i].size(); j++, index = (index+1)%k)
				build[i][rm[i][j]] = index, mark[i][index] = 1;
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < (int)add[i].size(); j++, index = (index+1)%k) {
				while(mark[i][index]) index = (index + 1) % k;
				build[i][add[i][j]] = index;
				mark[i][index] = 1;
			}
		}

		allocate_tickets(build);
		return ans;
	}

	return 0;
}

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