Submission #400935

#	Time	Username	Problem	Language	Result	Execution time	Memory
400935		priority_queue	Carnival Tickets (IOI20_tickets)	C++14	27 / 100	634 ms	54496 KiB

tickets

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

		 // first half is negative
		for (int j = 0; j < n/2; 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]++;
		}

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

		 //cerr  << total << "--" << endl;
	}

	allocate_tickets(s);

	return total;
}


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]--;
		}
	}


	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: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10