Submission #580835

#	Time	Username	Problem	Language	Result	Execution time	Memory
580835		joelau	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	749 ms	76116 KiB

tickets

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

long long A[1505], B[1505];
priority_queue< pair<long long,long long> > pq;
pair<long long,long long> lst[1505];

long long find_maximum(int k, vector<vector<int>> x) {
	long long N = x.size(), M = x[0].size(), val = 0;
	for (long long i = 0; i < N; ++i) {
		A[i] = k-1;
		pq.emplace(x[i][k-1]+x[i][M-1],i);
		for (long long j = 0; j < k; ++j) val -= x[i][j];
	}
	for (long long i = 0; i < k*N/2; ++i) {
		val += pq.top().first;
		long long n = pq.top().second; pq.pop();
		A[n]--;
		if (A[n] != -1) pq.emplace(x[n][A[n]]+x[n][A[n]+M-k],n);
	}
	for (long long i = 0; i < N; ++i) B[i] = A[i]+M-k+1, lst[i] = make_pair(M-B[i],i);
	vector< vector<int> > ans (N, vector<int>(M,-1));
	for (long long i = 0; i < k; ++i) {
		sort(lst,lst+N);
		for (long long j = 0; j < N/2; ++j) {
			long long n = lst[j].second;
			ans[n][A[n]] = i, A[n]--;
		}
		for (long long j = N/2; j < N; ++j) {
			long long n = lst[j].second;
			ans[n][B[n]] = i, B[n]++, lst[j].first--;
		}
	}
	allocate_tickets(ans);
	return val;
}

• 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