Submission #849516

#	Time	Username	Problem	Language	Result	Execution time	Memory
849516		IBory	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	387 ms	52816 KiB

tickets

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

const int MAX = 1505;
int L[MAX], R[MAX];

ll find_maximum(int K, vector<vector<int>> X) {
	int N = X.size();
	int M = X[0].size();
	ll ans = 0;
	vector<vector<int>> used;
	for (int i = 0; i < N; ++i) {
		vector<int> go(M, -1);
		used.push_back(go);
	}

	fill(L, L + N, 0);
	fill(R, R + N, M - 1);
	for (int k = 0; k < K; ++k) {
		vector<pii> T;
		ll init = 0;
		for (int i = 0; i < N; ++i) {
			init += X[i][R[i]];
			T.emplace_back(-X[i][L[i]] - X[i][R[i]], i);
		}
		sort(T.begin(), T.end(), greater<pii>());
		for (int i = 0; i < N / 2; ++i) {
			auto [v, id] = T[i];
			init += v;
			used[id][L[id]++] = k;
		}
		for (int i = N / 2; i < N; ++i) {
			auto [_, id] = T[i];
			used[id][R[id]--] = k;
		}
		ans += init;
	}

	allocate_tickets(used);
	return ans;
}

• 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