Submission #744741

#	Time	Username	Problem	Language	Result	Execution time	Memory
744741		josanneo22	Carnival Tickets (IOI20_tickets)	C++17	0 / 100	31 ms	3652 KiB

tickets

#include <bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
using namespace std;

#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second 
#include "tickets.h"
#include <vector>

long long find_maximum(int k, vector<vector<int>> x) {
	int n = x.size(), m = x[0].size();
	long long ans = 0;
	vector<pii> todo;
	for(int i=0;i<n;i++){
		for(int j=m-k;j<m;j++) ans += x[i][j];
		for(int j=0;j<k;j++) todo.pb({ -x[i][j] - x[i][m - k + j],i });
	}
	sort(todo.rbegin(),todo.rend());
	vector<int> num(n);
	for(int i=0;i<n*k/2;i++){
		num[todo[i].se]++;
		ans += todo[i].fi;
	}
	vector<vector<int>> ret(n, vector<int>(m, -1));
	vector<int> lo(n, 0), hi(n, m - 1);
	for(int i=0;i<k;i++) {
		vector<int> ha;
		int x = 0;
		for(int j=0;j<k;j++) {
			if (num[j] == k - i) {
				ret[j][lo[j]++] = i;
				num[j]--;
				x++;
			}
			else if (num[j] == 0) {
				ret[j][hi[j]--] = i;
			}
			else {
				ha.pb(j);
			}
		}
		for(auto&t:ha) {
			if (x < n / 2) {
				ret[t][lo[t]++] = i;
				num[t] --;
				x++;
			}
			else {
				ret[t][hi[t]--] = i;
			}
		}
		assert(x == n / 2);
	}
	allocate_tickets(ret);
	return ans;
}

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