Submission #824705

#	Time	Username	Problem	Language	Result	Execution time	Memory
824705		thimote75	Carnival Tickets (IOI20_tickets)	C++14	27 / 100	383 ms	51324 KiB

tickets

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

using idata = vector<int>;
using igrid = vector<idata>;

using di = pair<int, int>;
using vd = vector<di>;

int find_maximum(signed K, vector<vector<signed>> x) {
	int N = x.size(); int M = x[0].size(); int H = N >> 1;

	idata L(N, 0);
	idata R(N, M - 1);

	int result = 0;

	vector<vector<signed>> allocations(N, vector<signed>(M, -1));

	for (int k = 0; k < K; k ++) {
		int lcr = 0;

		vd compos;

		for (int i = 0; i < N; i ++) {
			lcr -= x[i][L[i]];

			compos.push_back({
				x[i][R[i]] + x[i][L[i]],
				i
			});

			allocations[i][L[i]] = k;
			L[i] ++;
		}

		sort(compos.rbegin(), compos.rend());
	
		for (int iC = 0; iC < H; iC ++) {
			lcr += compos[iC].first;

			int iV = compos[iC].second;
			L[iV] --;
			allocations[iV][L[iV]] = - 1;
			allocations[iV][R[iV]] = k;
			R[iV] --;
		}

		result += lcr;
	}

	allocate_tickets(allocations);

	return result;
}

• 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