Submission #578781

#	Time	Username	Problem	Language	Result	Execution time	Memory
578781		thiago_bastos	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	848 ms	113720 KiB

tickets

#include "tickets.h"
#include <vector>
#include <algorithm>
#include <tuple>
 
long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	long long prize = 0;
 
	auto answer = std :: vector<std :: vector<int>>(n, std :: vector<int>(m, -1));
	auto type = std :: vector<std :: vector<int>>(n, std :: vector<int>(m, 0));
	std :: vector<std :: vector<int>> sum(n), sub(n);
 
	std :: vector<std :: tuple<int, int, int>> a;
 
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < k; ++j) a.emplace_back(x[i][m - k + j] + x[i][j], i, j);
		for(int j = m - k; j < m; ++j) {
			type[i][j] = 1;
			prize += x[i][j];
		}
	}
 
	std :: sort(a.begin(), a.end());
 
	for(int i = 0; i < n * k / 2; ++i) {
		auto [v, x, y] = a[i];
		prize -= v;
		type[x][y + m - k] = 0; 
		type[x][y] = -1;
	}
 
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < m; ++j) {
			if(type[i][j] == -1) sub[i].push_back(j);
			else if(type[i][j] == 1) sum[i].push_back(j);
		}
	}
 
	while(--k >= 0) {
		int L = 0, R = 0;
		for(int i = 0; i < n; ++i) {
			if(!sum[i].empty() && !sub[i].empty()) continue;
			else if(!sum[i].empty()) {
				++R;
				answer[i][sum[i].back()] = k;
				sum[i].pop_back();
			} else {
				++L;
				answer[i][sub[i].back()] = k;
				sub[i].pop_back();
			}
		}
		for(int i = 0; i < n; ++i) {
			if(sum[i].empty() || sub[i].empty()) continue;
			if(L < n / 2) {
				++L;
				answer[i][sub[i].back()] = k;
				sub[i].pop_back();
			} else {
				++R;
				answer[i][sum[i].back()] = k;
				sum[i].pop_back();
			}
		}
	}
 
	allocate_tickets(answer);
 
	return prize;
}

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