Submission #391048

#	Time	Username	Problem	Language	Result	Execution time	Memory
391048		wind_reaper	Carnival Tickets (IOI20_tickets)	C++17	0 / 100	1 ms	332 KiB

tickets

#include <bits/stdc++.h>
#ifndef LOCAL
#include "tickets.h"
#endif

using namespace std;

#ifdef LOCAL
void allocate_tickets(vector<vector<int>> ans){
	int n = ans.size(), m = ans[0].size();
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++)
			cout << ans[i][j] << ' ';
		cout << '\n';
	}
}
#endif

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

	int64_t a = 0;

	priority_queue<array<int64_t, 4>> pq;
	vector<vector<int>> ans(n, vector<int>(m, -1));

	vector<priority_queue<int>> maximum_in_row(n);
	vector< priority_queue<int, vector<int>, greater<int>> > minimum_in_row(n);

	for(int i = 0; i < n; i++){
		for(int j = 0; j < k; j++){
			a -= int64_t(x[i][j]);
			ans[i][j] = j;
			minimum_in_row[i].push(j);
		}
		for(int j = m-1; j >= k; --j)
			maximum_in_row[i].push(j);

		pq.push({int64_t(x[i][k-1] + x[i][m-1]), i, k-1, m-1});
	}

	for(int i = 0; i < n*k / 2; i++){
		auto [delta, row, remove, add] = pq.top();
		pq.pop();
		maximum_in_row[i].pop();
		minimum_in_row[i].pop();
		maximum_in_row[i].push(remove);
		minimum_in_row[i].push(add);

		ans[row][add] = ans[row][remove];
		ans[row][remove] = -1;

		a += int64_t(delta);

		int nxtmin = minimum_in_row[row].top(), nxtmax = maximum_in_row[row].top();

		pq.push({x[row][nxtmin] + x[row][nxtmax], row, nxtmin, nxtmax});
	}

	allocate_tickets(ans);
	return a;
}

#ifdef LOCAL

int main(){
	int n, m, k;
	cin >> n >> m >> k;

	vector<vector<int>> x(n, vector<int>(m));
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			cin >> x[i][j];

	cout << find_maximum(k, x) << '\n';
}
#endif

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