Submission #1179052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179052		cot7302	Carnival Tickets (IOI20_tickets)	C++20	27 / 100	311 ms	51444 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
#define ALL(X) begin(X), end(X)

namespace {

using i64 = long long;
using namespace std;

template <class T>
using vec = vector<T>;

template <class T>
istream& operator>>(istream& is, vec<T>& X) {
  for (auto& x : X) {
    is >> x;
  }
  return is;
}

template <class T>
constexpr T infty = 0;

template <>
constexpr int infty<int> = 1'000'000'000;

template <>
constexpr i64 infty<i64> = 1'000'000'000'000'000'000;

}

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int N = size(x);
	int M = size(x[0]);
	vec<int> id(N);
	priority_queue<pair<int, int>> pq;
	i64 sum{};
	for (int i = 0; i < N; i++) {
		for (int j = M - k; j < M; j++) {
			sum += x[i][j];
		}
		pq.emplace(-x[i][0] - x[i][M - k], i);
	}
	for (int t = N * k / 2; t--; ) {
		auto [v, i] = pq.top(); pq.pop();
		sum += v;
		if (++id[i] < k) {
			pq.emplace(-x[i][id[i]] - x[i][M - id[i]], i);
		}
	}
	vec<vec<int>> answer(N, vec<int>(M, -1));
	vec<int> ord(N), id2(N);
	iota(ALL(ord), 0);
	for (int i = 0; i < N; i++) {
		id2[i] = M - k + id[i];
	}
	for (int t = 0; t < k; t++) {
		sort(ALL(ord), [&](int i, int j) {
			return id[i] > id[j];
		});
		for (int i = 0; i < N / 2; i++) {
			int j = ord[i];
			assert(id[j] > 0);
			answer[j][--id[j]] = t;
		}
		for (int i = N / 2; i < N; i++) {
			int j = ord[i];
			assert(id2[j] < M);
			answer[j][id2[j]++] = t;
		}
	}
	allocate_tickets(answer);
	return sum;
}

• 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