제출 #460373

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

tickets

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

using namespace std;

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

	vector<vector<int>> ans(N, vector<int>(M, -1));

	long long sum = 0;

	priority_queue<array<int64_t, 3>> pq;

	for(int i = 0; i < N; i++){
		for(int j = 0; j < k; j++){
			pq.push({x[i][j] +  x[i][M-k+j], i, j});
			ans[i][j] = 0;
			sum -= x[i][j];
		}
	}

	for(int _ = 0; _ < (N * 1LL * k) / 2; _++){
		auto [v, i, j] = pq.top();
		pq.pop();
		sum += v;
		ans[i][j] = -1;
		ans[i][M - k + j] = 1;
	}

	int l[N], r[N]; array<int, 2> arr[N];

	for(int i = 0; i < N; i++){
		arr[i][0] = 0;
		for(int j = 0; j < M; j++){
			if(ans[i][j] == 1){
				arr[i][0]++;
				r[i] = M - 1;
			}
			else if(ans[i][j] == 0) l[i] = 0;
		}
		arr[i][1] = i;
	}

	for(int i = 0; i < k; i++){
		sort(arr, arr + N);
		for(int j = 0; j < N; j++){
			int col = arr[j][1];

			if(j < N / 2) {
				// assert(ans[col][l[col]] == 0);
				ans[col][l[col]++] = i;
			}
			else{
				// assert(ans[col][r[col]] == 1);
				ans[col][r[col]--] = i;
				arr[j][0]--;
			}
		}
	}

	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