Submission #1039747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039747		AmirAli_H1	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	616 ms	141448 KiB

tickets

// In the name of Allah

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

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1500 + 4;

int n, m, k;
vector<vector<int>> ans;
vector<pll> Ax[maxn];
ll A[maxn][maxn], sm[maxn];
int valx[maxn]; ll res = 0;
priority_queue<pll> qu;
vector<int> ls1[maxn], ls2[maxn];

ll find_maximum(int k, vector<vector<int>> Rx) {
	n = len(Rx); m = len(Rx[0]);
	
	for (int i = 0; i < n; i++) {
		Ax[i].resize(m);
		for (int j = 0; j < m; j++) Ax[i][j] = Mp(Rx[i][j], j);
		sort(all(Ax[i]));
		
		sm[0] = 0;
		for (int j = 0; j < m; j++) sm[j + 1] = sm[j] + Ax[i][j].F;
		
		for (int j = 0; j <= k; j++) {
			A[i][j] = (sm[m] - sm[m - j]) - sm[k - j];
		}
		valx[i] = 0; res += A[i][valx[i]];
		if (valx[i] + 1 <= k) {
			qu.push(Mp(A[i][valx[i] + 1] - A[i][valx[i]], i));
		}
	}
	
	int R = (n * k) / 2;
	while (R--) {
		auto f = qu.top(); qu.pop();
		res += f.F;
		int i = f.S; valx[i]++;
		if (valx[i] + 1 <= k) {
			qu.push(Mp(A[i][valx[i] + 1] - A[i][valx[i]], i));
		}
	}
	
	ans.resize(n);
	for (int i = 0; i < n; i++) {
		ans[i].resize(m); fill(all(ans[i]), -1);
	}
	for (int i = 0; i < n; i++) {
		int j = valx[i];
		for (int r = 0; r < k - j; r++) ls1[i].pb(Ax[i][r].S);
		for (int r = m - j; r < m; r++) ls2[i].pb(Ax[i][r].S);
		reverse(all(ls1[i]));
	}
	
	for (int T = 0; T < k; T++) {
		int T1 = n / 2, T2 = n / 2;
		for (int i = 0; i < n; i++) {
			if (len(ls2[i]) == 0) {
				int j = ls1[i].back(); ls1[i].pop_back();
				ans[i][j] = T;
				T1--;
			}
			else if (len(ls1[i]) == 0) {
				int j = ls2[i].back(); ls2[i].pop_back();
				ans[i][j] = T;
				T2--;
			}
		}
		for (int i = 0; i < n; i++) {
			if (len(ls1[i]) + len(ls2[i]) != k - T) continue;
			if (T1 > 0) {
				int j = ls1[i].back(); ls1[i].pop_back();
				ans[i][j] = T;
				T1--;
			}
			else {
				int j = ls2[i].back(); ls2[i].pop_back();
				ans[i][j] = T;
				T2--;
			}
		}
	}
	
	allocate_tickets(ans);
	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