Submission #605165

#	Time	Username	Problem	Language	Result	Execution time	Memory
605165		Tigryonochekk	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	514 ms	73180 KiB

tickets

#include <iostream>
#include <algorithm>
#include "tickets.h"
#include <vector>
#define ll long long
using namespace std;
const ll inf = 1e18 + 69;
#define pii pair<ll, int>

vector<vector<int>> answer;
ll ans;

vector<pii> wtf[1502];

long long find_maximum(int k, vector<vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	answer.resize(n);
	for (int i = 0; i < n; i++) {
		answer[i].resize(m, -1);
	}
	if (k == 1) {
		vector<pii> d(n);
		for (int i = 0; i < n; i++) {
			d[i] = pii(x[i][m - 1] + x[i][0], i);
			ans += x[i][m - 1];
		}
		sort(d.begin(), d.end());
		vector<int> v(n);
		for (int i = 0; i < n / 2; i++) {
			int ind = d[i].second;
			answer[ind][0] = 0;
			ans -= d[i].first;
		}
		for (int i = n / 2; i < n; i++) {
			int ind = d[i].second;
			answer[ind][m - 1] = 0;
		}
	}
	else if (k == m) {
		vector<pii> all;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				all.push_back(pii(x[i][j], i * m + j));
			}
		}
		sort(all.begin(), all.end());
		for (int i = 0; i < n * m / 2; i++) {
			ans -= all[i].first;
		}
		for (int i = n * m / 2; i < n * m; i++) {
			ans += all[i].first;
		}
		pii mid = all[n * m / 2];
		//vector<vector<int>> sign(n);
		vector<int> ty(n);
		for (int i = 0; i < n; i++) {
			if (pii(x[i][0], i * m) >= mid) {
				ty[i] = 1;
			}
			else if (pii(x[i][m - 1], i * m + m - 1) < mid) {
				ty[i] = 2;
			}
		}
		/*for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				sign[i].push_back((pii(x[i][j], i * m + j) >= mid) + 1);
			}
		}*/
		vector<int> plyus(n, m - 1), minus(n);
		for (int j = 0; j < m; j++) {
			int a = 0, b = 0;
			for (int i = 0; i < n; i++) {
				if (ty[i] == 1) {
					a++;
					answer[i][j] = j;
				}
				if (ty[i] == 2) {
					b++;
					answer[i][j] = j;
				}
			}
			for (int i = 0; i < n; i++) {
				if (!ty[i]) {
					if (a + 1 < n / 2 && pii(x[i][plyus[i]], i * m + j) >= mid) {
						answer[i][plyus[i]] = j;
						plyus[i]--;
					}
					else {
						answer[i][minus[i]] = j;
						minus[i]++;
					}
				}
			}
		}
	}
	allocate_tickets(answer);
	return ans;
}

/*
2 3 2 
0 2 5 
1 1 3 
*/

• 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