Submission #404710

#	Time	Username	Problem	Language	Result	Execution time	Memory
404710		bipartite_matching	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	837 ms	54884 KiB

tickets

#include <bits/stdc++.h>

#define forint(i, N) for (int i = 0; i < (N); i++)

using namespace std;

void allocate_tickets(vector< vector<int> > s);

long long find_maximum(int k, vector< vector<int> > x) {

	int n = x.size();
	int m = x[0].size();

	//long long ans = 0;

	//vector< vector<bool> > minval(n, vector<bool>(k, true));
	//vector< vector<bool> > plusval(n, vector<bool>(k, false));

	vector< pair<int, int> > last_coor(n, make_pair(m - 1, k - 1));

	priority_queue< pair<int, int> > q;
	
	forint(i, n) {
		q.push(make_pair(x[i][k - 1] + x[i][m - 1], i));
	}

	forint(i, k * n / 2) {
		auto pos = q.top();
		q.pop();

		//minval[pos.second][last_coor[pos.second].first] = false;

		last_coor[pos.second].first--;
		last_coor[pos.second].second--;

		if (last_coor[pos.second].second >= 0) {
			q.push({x[pos.second][last_coor[pos.second].first] + x[pos.second][last_coor[pos.second].second], pos.second});
		}

	}

	/*
	for (auto& i : minval) {
		for (auto& j : i) {
			cerr << minval << endl;
		}
	}
	

	for (auto a : last_coor) {
		cerr << a.first << "---" << a.second << endl;
	}
*/

	vector< vector<int> > round(n, vector<int> (m, -1));	

	long long val = 0;

	forint(i, k) {

		vector< pair<int, int> > v(n);
		forint(j, n) {
			v[j].first = last_coor[j].first;
			v[j].second = j;
		}

		//sort(v.begin(), v.end());
		nth_element(v.begin(), v.begin() + n/2, v.end());

		for(int j = 0; j < n/2; j++) {
			val += x[v[j].second][last_coor[v[j].second].first + 1];
			round[v[j].second][last_coor[v[j].second].first + 1] = i;
			last_coor[v[j].second].first++;
		}

		for(int j = n/2; j < n; j++) {
			val -= x[v[j].second][last_coor[v[j].second].second];
			round[v[j].second][last_coor[v[j].second].second] = i;
			last_coor[v[j].second].second--;
		}

	}


	
	allocate_tickets(round);
	
	return val;
}

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23
• Subtask 7: 10 / 10