Submission #1233040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233040		colossal_pepe	Carnival Tickets (IOI20_tickets)	C++20	27 / 100	317 ms	69160 KiB

tickets

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

using ll = long long;

int n, m, k;
vector<vector<ll>> x;

vector<vector<int>> getAllocation() {
	vector<vector<int>> alloc(n, vector<int>(m, 0));
	vector<tuple<int, int, int>> candies;
	for (int i = 0; i < n; i++) {
		candies.push_back(make_tuple(i, 0, m - 1));
	}
	for (int i = 1; i <= k; i++) {
		sort(candies.begin(), candies.end(), [&](auto t1, auto t2) {
			auto [i1, l1, r1] = t1;
			auto [i2, l2, r2] = t2;
			return x[i1][l1] + x[i1][r1] < x[i2][l2] + x[i2][r2];
		});
		for (int j = 0; j < n; j++) {
			auto &[idx, l, r] = candies[j];
			if (j < n / 2) alloc[idx][l++] = -i;
			else alloc[idx][r--] = i;
		}
	}
	return alloc;
}

ll find_maximum(int K, vector<vector<int>> X) {
	n = X.size(), m = X[0].size(), k = K;
	x.resize(n, vector<ll>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			x[i][j] = X[i][j];
		}
	}
	vector<vector<int>> alloc = getAllocation();
	ll score = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (alloc[i][j] < 0) {
				score -= x[i][j];
				alloc[i][j] = -alloc[i][j] - 1;
			} else if (alloc[i][j] > 0) {
				score += x[i][j];
				alloc[i][j] = alloc[i][j] - 1;
			} else alloc[i][j] = -1;
		}
	}
	allocate_tickets(alloc);
	return score;
}

• 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