Submission #431439

#	Time	Username	Problem	Language	Result	Execution time	Memory
431439		saleh	Carnival Tickets (IOI20_tickets)	C++17	16 / 100	814 ms	51392 KiB

tickets

#include "tickets.h"//
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int INF = 1e10;

int n, m, jav;
vector<int> chi, zz, cho;

long long find_maximum(int32_t k, vector<vector<int32_t>> x) {
	n = x.size();
	m = x[0].size();
	if (k != 1 || m <= 1) return 8;
	long long jav = 0;
	vector<vector<int32_t>> answer;
	zz.resize(n);
	for (int i = 0; i < n; i++) {
		vector<int32_t> row(m);
		for (int j = 0; j < m; j++)
			row[j] = -1;
		chi.push_back(x[i][0]);
		cho.push_back(x[i].back());
		answer.push_back(row);
	}
	sort(chi.begin(), chi.end());
	vector<int> fnd;
	for (int i = 0; i < n; i++) {
		int ct = 0, jt = 0;
		for (auto j : chi) if (j <= x[i][0]) ct++;
		if (ct < n / 2) continue;
		ct = 0;
		for (auto j : cho) if (j >= x[i][0]) ct++;
		if (ct < n / 2) continue;
		for (int j = 0; j < n; j++) {
			if (x[j].back() < x[i][0]) {
				zz[j] = INF;
				continue;
			}
			if (x[j][0] > x[i][0]) {
				zz[j] = -INF;
				continue;
			}
			zz[j] = - x[j].back() - x[j][0] + (x[i][0] << 1);
		}
		zz[i] = INF + 8;
		vector<int> ch;
		for (int i = 0; i < n; i++) ch.push_back(i);
		sort(ch.begin(), ch.end(), [](int x, int y) { return zz[x] > zz[y]; });
		for (int i = 0; i < n / 2; i++) jt += x[i][0] - x[ch[i]][0];
		for (int i = 0; i < n / 2; i++) jt += x[ch[i + n / 2]].back() - x[i][0];
		if (jt > jav) {
			jav = jt;
			fnd = ch;
		}
	}
	for (int i = 0; i < n / 2; i++) answer[fnd[i]][0] = 0;
	for (int i = 0; i < n / 2; i++) answer[fnd[i + n / 2]][m - 1] = 0;
	allocate_tickets(answer);//
	return jav;
}

//int32_t main() {}//

• Subtask 1: 0 / 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