제출 #589398

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
589398		Lucpp	카니발 티켓 (IOI20_tickets)	C++17	100 / 100	722 ms	104260 KiB

tickets

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

ll find_maximum(int k, vector<vector<int>> x) {
	int n = (int)x.size();
	int m = (int)x[0].size();
	ll sum = 0;
	priority_queue<pair<ll, int>> pq;
	vector<int> taken(n, 0);
	vector<vector<pair<int, int>>> y(n, vector<pair<int, int>>(m));
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++) y[i][j] = {x[i][j], j};
		sort(x[i].begin(), x[i].end());
		sort(y[i].begin(), y[i].end());
		for(int j = 0; j < k; j++) sum -= x[i][j];
		pq.emplace(x[i][m-1]+x[i][k-1], i);
	}
	for(int i = 0; i < n*k/2; i++){
		auto [v, j] = pq.top(); pq.pop();
		sum += v;
		taken[j]++;
		if(taken[j] < k){
			pq.emplace(x[j][m-1-taken[j]]+x[j][k-1-taken[j]], j);
		}
	}
	vector<vector<int>> ans(n, vector<int>(m, -1));
	vector<stack<int>> b(n), s(n);
	for(int i = 0; i < n; i++){
		for(int j = 0; j < k-taken[i]; j++) s[i].push(y[i][j].second);
		for(int j = m-taken[i]; j < m; j++) b[i].push(y[i][j].second);
	}
	for(int r = 0; r < k; r++) {
		int t = 0;
		for(int i = 0; i < n; i++){
			if(b[i].empty()) ans[i][s[i].top()] = r;
			if(s[i].empty()) ans[i][b[i].top()] = r, t++;
		}
		for(int i = 0; i < n; i++){
			if(b[i].empty()) s[i].pop();
			else if(s[i].empty()) b[i].pop();
			else{
				if(t < n/2){
					ans[i][b[i].top()] = r;
					b[i].pop();
					t++;
				}
				else{
					ans[i][s[i].top()] = r;
					s[i].pop();
				}
			}
		}
	}
	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