Submission #1239532

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239532		AMnu	Carnival Tickets (IOI20_tickets)	C++20	100 / 100	462 ms	54324 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int MAXN = 1505;

int N, M, P[MAXN];
ll sum;
pii S[MAXN];
priority_queue <pii> Q;

ll find_maximum(int K,vector<vector<int>> A) {
	N = A.size();
	M = A[0].size();
	vector<vector<int>> ans(N,vector<int>(M,-1));
	for (int i=0;i<N;i++) {
		for (int j=0;j<K;j++) {
			sum -= A[i][j];
		}
		Q.push({A[i][K-1]+A[i][M-1],i});
	}
	for (int i=0;i<N*K;i+=2) {
		pii T = Q.top();
		Q.pop();
		sum += T.fi;
		P[T.se]++;
		if (P[T.se] < K) {
			Q.push({A[T.se][K-1-P[T.se]]+A[T.se][M-1-P[T.se]],T.se});
		}
	}
	for (int i=0;i<K;i++) {
		for (int j=0;j<N;j++) {
			S[j] = {P[j],j};
		}
		sort(S,S+N);
		for (int j=0;j<N/2;j++) {
			ans[S[j].se][K-i-P[S[j].se]-1] = i;
		}
		for (int j=N/2;j<N;j++) {
			ans[S[j].se][M-P[S[j].se]] = i;
			P[S[j].se]--;
		}
	}
	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