Submission #1223717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223717		Tob	Carnival Tickets (IOI20_tickets)	C++20	100 / 100	676 ms	86668 KiB

tickets

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

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

ll find_maximum(int k, vector <vector <int> > x) {
	int n = x.size(), m = x[0].size();
	vector <vector <int> > r(n, vector <int> (m, -1));
	vector <vector <pii> > v(n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) v[i].pb({x[i][j], j});
		sort(all(v[i]));
	}
	vector <int> c(n, 0);
	priority_queue <pii, vector <pii>, greater <pii> > q;
	ll res = 0;
	for (int i = 0; i < n; i++) {
		for (int j = m-k; j < m; j++) res += v[i][j].F;
		q.push({v[i][0].F+v[i][m-k].F, i});
	}
	for (int i = 0; i < n*k/2; i++) {
		pii p = q.top();
		q.pop();
		c[p.S]++;
		res -= p.F;
		if (c[p.S] < k) q.push({v[p.S][c[p.S]].F+v[p.S][m-k+c[p.S]].F, p.S});
	}
	for (int i = 0, d = 0; i < n; i++) {
		for (int j = 0; j < c[i]; j++, d = (d+1)%k) r[i][v[i][j].S] = d;
		for (int j = m-k+c[i], e = d; j < m; j++, e = (e+1)%k) r[i][v[i][j].S] = e;
	}
	allocate_tickets(r);
	return res;
}

• 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