Submission #466331

#	Time	Username	Problem	Language	Result	Execution time	Memory
466331		armand	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	958 ms	84956 KiB

tickets

#include "tickets.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;

struct elem
{
	int row, colm, colM, val;
};

bool operator<(const elem& x, const elem& y)
{
	return x.val < y.val;
}

long long find_maximum(int k, std::vector<std::vector<int>> x)
{
	std::vector<std::vector<int>> a;
	int n = x.size();
	int m = x[0].size();
	int i, j;
	long long res = 0;
	elem e;
	vector<int> neg(n, 0), pos(n, 0);
	vector<int> neg_idx(n), pos_idx(n);
	vector<pair<int, int> > p(n);
	std::vector<std::vector<int>> answer;
	for (i = 0; i < n; i++) {
		std::vector<int> row(m, -1);
		answer.push_back(row);
		a.push_back(row);
	}
	for(i=0; i<n; i++)
		for (j = 0; j < k; j++) {
			a[i][j] = -1;
			neg[i]++;
			res -= x[i][j];
		}
	priority_queue<elem> pq;
	for (i = 0; i < n; i++) {
		e.row = i;
		e.colm = k - 1;
		e.colM = m - 1;
		e.val = x[i][k - 1] + x[i][m - 1];
		pq.push(e);
	}
	for (i = 0; i < n*k / 2; i++) {
		e = pq.top();
		pq.pop();
		res += e.val;
		a[e.row][e.colm] = 0;
		a[e.row][e.colM] = 1;
		if (e.colm - 1 >= 0) {
			e.colm--;
			e.colM--;
			e.val = x[e.row][e.colm] + x[e.row][e.colM];
			pq.push(e);
		}
	}
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			if (a[i][j] < 0)
				neg[i]++;
			else if (a[i][j] > 0)
				pos[i]++;
	for (i = 0; i < n; i++) {
		neg_idx[i] = -1;
		pos_idx[i] = m;
	}
	for (i = 0; i < k; i++) {
		for (j = 0; j < n; j++) {
			p[j].first = pos[j];
			p[j].second = j;
		}
		sort(p.begin(), p.end());
		for (j = 0; j < n / 2; j++) {
			neg_idx[p[j].second]++;
			answer[p[j].second][neg_idx[p[j].second]] = i;
			neg[p[j].second]--;
		}
		for (j = n / 2; j < n; j++) {
			pos_idx[p[j].second]--;
			answer[p[j].second][pos_idx[p[j].second]] = i;
			pos[p[j].second]--;
		}
	}
/*	cerr << "a=\n";
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++)
			cerr << a[i][j] << ' ';
		cerr << endl;
	}
	*/
	allocate_tickets(answer);
	return res;
}

• 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