Submission #1078085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078085		mickey080929	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	366 ms	69136 KiB

tickets

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

using namespace std;
typedef long long ll;

void allocate_tickets( std::vector<std::vector<int>> _d);

ll find_maximum(int k, vector<vector<int>> x) {
	int n = x.size(), m = x[0].size();
	vector<vector<pair<int,int>>> x2(n, vector<pair<int,int>>(m));
	for (int i=0; i<n; i++) {
		for (int j=0; j<m; j++) {
			x2[i][j] = {x[i][j], j};
		}
		sort(x2[i].begin(), x2[i].end());
	}
	vector<vector<int>> ans(n, vector<int>(m, -1));
	vector<int> l(n, 0), r(n, m-1);
	ll sum = 0;
	for (int i=0; i<k; i++) {
		vector<int> id(n);
		iota(id.begin(), id.end(), 0);
		sort(id.begin(), id.end(), [&] (int &u, int &v) { 
			return x2[u][l[u]].first + x2[u][r[u]].first < x2[v][l[v]].first + x2[v][r[v]].first;
		});
		for (int j=0; j<n/2; j++) {
			ans[id[j]][x2[id[j]][l[id[j]]].second] = i;
			sum -= x2[id[j]][l[id[j]]].first;
			l[id[j]] ++;
		}
		for (int j=n/2; j<n; j++) {
			ans[id[j]][x2[id[j]][r[id[j]]].second] = i;
			sum += x2[id[j]][r[id[j]]].first;
			r[id[j]] --;
		}
	}
	allocate_tickets(ans);
	return sum;
}

• 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