Submission #300207

#	Time	Username	Problem	Language	Result	Execution time	Memory
300207		sjimed	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	1216 ms	66424 KiB

tickets

#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(NULL)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define all(v) (v).begin(), (v).end()
#define pre(a) cout<<fixed; cout.precision(a)
#define mp make_pair

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll inf = 1e9;
const ll INF = 1e18;

vector<int> l[1510];
vector<int> s[1510];

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row(m, 0);
		answer.push_back(row);
	}

	ll ret = 0;
	int cnt[1510] = {};
	priority_queue<pii> pq;
	for(int i=0; i<n; i++) {
		for(int j=0; j<k; j++) {
			ret -= x[i][j];
			answer[i][j] = -1;
		}
		cnt[i] = k;
		pq.em(x[i][cnt[i]-1] + x[i][m - 1 - k + cnt[i]] , i);
	}

	int T = n/2 * k;

	while(T--) {
		int i = pq.top().se;
		ret += pq.top().fi;
		
		answer[i][cnt[i]-1]++;
		answer[i][m - 1 - k + cnt[i]]++;
		cnt[i]--;
		pq.pop();

		if(cnt[i]) pq.em(x[i][cnt[i]-1] + x[i][m - 1 - k + cnt[i]], i);
	}

	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			if(answer[i][j] == 1) l[i].eb(j);
			else if(answer[i][j] == -1) s[i].eb(j);

			answer[i][j] = -1;
		}
	}

	for(int i=0; i<k; i++) {
		vector<int> t;
		for(int j=0; j<n; j++) t.eb(j);

		sort(all(t), [&] (int a, int b) {
			return l[a].size() < l[b].size();
		});

		for(int j=0; j<n/2; j++) {
			answer[t.back()][l[t.back()].back()] = i;
			l[t.back()].pop_back();
			t.pop_back();
		}

		sort(all(t), [&] (int a, int b) {
			return s[a].size() < s[b].size();
		});

		for(int j=0; j<n/2; j++) {
			answer[t.back()][s[t.back()].back()] = i;
			s[t.back()].pop_back();
			t.pop_back();
		}
	}

	allocate_tickets(answer);
	return ret;
}

• 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