Submission #401649

#	Time	Username	Problem	Language	Result	Execution time	Memory
401649		priority_queue	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	870 ms	72932 KiB

tickets

// ioi 2020, day 1, p3 ticket

#include <bits/stdc++.h>

using namespace std;

#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();

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

	vector<int> min_index(n, k-1);
	vector<int> max_index(n, m-1);

	vector<pair<long long, int>> increase(n);

	long long total = 0;

	/*
	forint(i, k) {
		forint(j, n) {			
			increase[j].first = x[j][min_index[j]] + x[j][max_index[j]];
			increase[j].second = j;
		}
		nth_element(increase.begin(), increase.begin() + n/2, increase.end());

		for (int j = n/2; j < n; j++) {
			max_index[increase[j].second]--;
			min_index[increase[j].second]--;
		}
	}
	*/

	priority_queue< pair<int, int> > pq;
	forint(j, n) {			
		pq.push({x[j][min_index[j]] + x[j][max_index[j]], j});
		//increase[j].second = j;
	}

	forint(i, k*n/2) {
		auto t = pq.top();
		pq.pop();
		max_index[t.second]--;
		min_index[t.second]--;

		if (min_index[t.second] >= 0) {
			pq.push({x[t.second][min_index[t.second]] + x[t.second][max_index[t.second]], t.second});
		}
	}


	forint(i, k) {
		forint(j, n) {			
			increase[j].first = max_index[j];
			increase[j].second = j;
		}
		nth_element(increase.begin(), increase.begin() + n/2, increase.end());

		for (int j = 0; j < n/2; j++) {		 	  
			max_index[increase[j].second]++;
			total += x[increase[j].second][max_index[increase[j].second]];
			s[increase[j].second][max_index[increase[j].second]] = i;
		}
		
		for (int j = n/2; j < n; j++) {
			total -= x[increase[j].second][min_index[increase[j].second]];
			s[increase[j].second][min_index[increase[j].second]] = i;
			min_index[increase[j].second]--;
		}
	}


	allocate_tickets(s);

	return total;
}

• 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