제출 #1187829

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1187829		hamzabc	카니발 티켓 (IOI20_tickets)	C++20	27 / 100	503 ms	71096 KiB

tickets

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


using namespace std;
#define all(x) x.begin(), x.end()


long long find_maximum(int k, vector<vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	vector<vector<int>> answer(n, vector<int>(m, -1));
	vector<array<int, 3>> arr(n * m);
	k = min(k, m);
	for (int i = 0; i < n * m; i++){
		arr[i][0] = x[i / m][i % m];
		arr[i][1] = i / m;
		arr[i][2] = i % m;
	}
	sort(all(arr));
	vector<vector<array<int, 5>>> mainarray(n, vector<array<int, 5>>(k));
	vector<int> indd(n);
	int ort = arr[arr.size() / 2][0];
	for (int i = 0; i < arr.size(); i++){
		if (indd[arr[i][1]] < k){
			mainarray[arr[i][1]][indd[arr[i][1]]][0] = ort - arr[i][0];
			mainarray[arr[i][1]][indd[arr[i][1]]][1] = arr[i][1];
			mainarray[arr[i][1]][indd[arr[i][1]]][2] = arr[i][2];
			indd[arr[i][1]]++;
		}
	}
	for (int i = arr.size() - 1; i >= 0; i--){
		if (indd[arr[i][1]] > 0){
			indd[arr[i][1]]--;
			mainarray[arr[i][1]][indd[arr[i][1]]][0] -= arr[i][0] - ort;
			mainarray[arr[i][1]][indd[arr[i][1]]][3] = arr[i][1];
			mainarray[arr[i][1]][indd[arr[i][1]]][4] = arr[i][2];
		}
	}
	priority_queue<array<int, 2>> pque;
	for (int i = 0; i < n; i++){
		pque.push({ mainarray[i][0][0], i });
	}
	for (int i = 0; i < n * k / 2; i++){
		auto f = pque.top();
		pque.pop();
		indd[f[1]]++;
		if (indd[f[1]] < k){
			pque.push({ mainarray[f[1]][indd[f[1]]][0], f[1] });
		}
	}
	vector<array<int, 2>> lft, rgt;
	long long ret = 0;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < indd[i]; j++){
			ret -= x[mainarray[i][j][1]][mainarray[i][j][2]];
			lft.push_back({ mainarray[i][j][1], mainarray[i][j][2] });
		}
		for (int j = indd[i]; j < k; j++){
			ret += x[mainarray[i][j][3]][mainarray[i][j][4]];
			rgt.push_back({ mainarray[i][j][3], mainarray[i][j][4] });
		}
	}
	for (int i = 0; i < rgt.size(); i++){
		answer[rgt[i][0]][rgt[i][1]] = i % k;
	}
	for (int i = 0; i < lft.size(); i++){
		answer[lft[i][0]][lft[i][1]] = i % k;
	}
	allocate_tickets(answer);
	return ret;
}

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