Submission #1250503

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250503		NikoBaotic	Team Contest (JOI22_team)	C++20	100 / 100	996 ms	129712 KiB

team

#include "bits/stdc++.h"

using namespace std;

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

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

const int N = 2e5 + 10;
const int K = 30;

int n;
int x[N];
int y[N];
int z[N];
bool k[N];
bool us[N];
vector<int> vx[N * 3];
vector<int> vy[N * 3];
vector<int> vz[N * 3];
int oc[N];

int main() {
	FIO;
	
	cin >> n;
	
	multiset<pii> sx, sy, sz;
	map<int, int> conv;
	set<int> se;

	int cur = 0;

	for (int i = 0; i < n; i++) {
		cin >> x[i] >> y[i] >> z[i];

		sx.insert({x[i], i});
		sy.insert({y[i], i});
		sz.insert({z[i], i});

		se.insert(x[i]);
		se.insert(y[i]);
		se.insert(z[i]);
	}

	for (int l : se) {
		conv[l] = cur++;
	}

	for (int i = 0; i < n; i++) {
		vx[conv[x[i]]].pb(i);
		vy[conv[y[i]]].pb(i);
		vz[conv[z[i]]].pb(i);
	}

	int bmx = -1;
	int bmy = -1;
	int bmz = -1;

	set<int> rem;	

	while (sz(sx)) {
		int mx = prev(sx.end())->F;
		int my = prev(sy.end())->F;
		int mz = prev(sz.end())->F;

		if (mx != bmx) {
			for (int l : vx[conv[mx]]) {
				oc[l]++;

				if (oc[l] > 1) {
					rem.insert(l);	
				}
			}
		}

		if (my != bmy) {
			for (int l : vy[conv[my]]) {
				oc[l]++;

				if (oc[l] > 1) {
					rem.insert(l);	
				}
			}
		}

		if (mz != bmz) {
			for (int l : vz[conv[mz]]) {
				oc[l]++;

				if (oc[l] > 1) {
					rem.insert(l);	
				}
			}
		}

		bool c = 0;

		for (int l : rem) {
			if (!k[l]) {
				sx.erase(sx.find({x[l], l}));
				sy.erase(sy.find({y[l], l}));
				sz.erase(sz.find({z[l], l}));

				k[l] = 1;
				c = 1;
			}
		}

		rem.clear();

		bmx = mx;
		bmy = my;
		bmz = mz;

		if (c == 0) break;
	}

	int cnt = K;

	while (sz(sx) and cnt) {
		us[prev(sx.end())->S] = 1;
		sx.erase(prev(sx.end()));
		cnt--;	
	}

	cnt = K;
	
	while (sz(sy) and cnt) {
		us[prev(sy.end())->S] = 1;
		sy.erase(prev(sy.end()));
		cnt--;	
	}

	cnt = K;

	while (sz(sz) and cnt) {
		us[prev(sz.end())->S] = 1;
		sz.erase(prev(sz.end()));
		cnt--;
	}

	vector<int> inc;

	for (int i = 0; i < n; i++) {
		if (us[i]) inc.pb(i);
	}

	int ans = -1;

	for (int i = 0; i < sz(inc); i++) {
		for (int j = 0; j < sz(inc); j++) {
			for (int l = 0; l < sz(inc); l++) {
				int f = inc[i];
				int s = inc[j];
				int t = inc[l];

				if (x[f] <= x[s] or x[f] <= x[t]) continue;
				if (y[s] <= y[f] or y[s] <= y[t]) continue;
				if (z[t] <= z[s] or z[t] <= z[f]) continue;

				ans = max(ans, x[f] + y[s] + z[t]);
			}
		}
	}

	cout << ans << endl;

	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 27 / 27