Submission #823016

#	Time	Username	Problem	Language	Result	Execution time	Memory
823016		ymm	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	695 ms	83592 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;

long long find_maximum(int k, std::vector<std::vector<int>> _x) {
	priority_queue<pll> pq;
	int n = _x.size();
	int m = _x[0].size();
	vector<vector<pii>> x;
	Loop (i,0,n) {
		x.emplace_back();
		Loop (j,0,m)
			x.back().push_back({_x[i][j], j});
		sort(x.back().begin(), x.back().end());
	}
	ll sum = 0;
	Loop (i,0,n) {
		Loop (j,0,k)
			sum -= x[i][j].first;
		pq.push({x[i][k-1].first + x[i][m-1].first, i});
	}
	vector<int> nxt(n, k);
	Loop (_,0,n*k/2) {
		auto [val, i] = pq.top();
		pq.pop();
		sum += val;
		--nxt[i];
		if (nxt[i])
			pq.push({x[i][nxt[i]-1].first + x[i][nxt[i]+m-k-1].first, i});
	}
	std::vector<std::vector<int>> ans(n, vector<int>(m, -1));
	vector<int> neg(n), pos(n);
	Loop (r,0,k) {
		vector<int> ne, po, bo;
		Loop (i,0,n) {
			if (neg[i] == nxt[i])
				po.push_back(i);
			else if (pos[i] == k - nxt[i])
				ne.push_back(i);
			else
				bo.push_back(i);
		}
		Loop (_,0,n/2) {
			auto &vec = ne.size()? ne: bo;
			int i = vec.back();
			vec.pop_back();
			ans[i][x[i][neg[i]++].second] = r;
		}
		Loop (_,0,n/2) {
			auto &vec = po.size()? po: bo;
			int i = vec.back();
			vec.pop_back();
			ans[i][x[i][m-1-(pos[i]++)].second] = r;
		}
	}
	allocate_tickets(ans);
	return sum;
}

• 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