Submission #1244034

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244034		Tob	Team Contest (JOI22_team)	C++20	37 / 100	100 ms	63316 KiB

team

#include <bits/stdc++.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 <ll, ll> pii;

const int N = 4007;

int n;
int a[N], b[N], c[N], sa[N], sb[N], ia[N], f[N][N];

int main () {
	FIO;
	cin >> n;
	
	vector <int> aa, bb;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i] >> c[i];
		aa.pb(a[i]);
		bb.pb(b[i]);
		ia[i] = i;
	}
	sort(ia, ia+n, [&](int x, int y){return a[x] < a[y];});
	sort(all(aa));
	sort(all(bb));
	aa.erase(unique(all(aa)), aa.end());
	bb.erase(unique(all(bb)), bb.end());
	
	for (int i = 0; i < n; i++) {
		sa[i] = lower_bound(all(aa), a[i])-aa.begin();
		sb[i] = lower_bound(all(bb), b[i])-bb.begin();
	}
	
	memset(f, -1, sizeof f);
	for (int i = 0; i < n; i++) {
		f[sa[i]+1][sb[i]+1] = max(f[sa[i]+1][sb[i]+1], c[i]);
	}
	for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) {
		if (i) f[i][j] = max(f[i][j], f[i-1][j]);
		if (j) f[i][j] = max(f[i][j], f[i][j-1]);
	}
	
	int res = -1;
	for (int i = 0; i < n; i++) {
		int x = ia[i];
		for (int j = 0; j < i; j++) if (a[ia[j]] < a[x] && b[ia[j]] > b[x]) {
			int y = ia[j];
			if (f[sa[x]][sb[y]] != -1 && f[sa[x]][sb[y]] > max(c[x], c[y])) res = max(res, f[sa[x]][sb[y]]+a[x]+b[y]);
		}
	}
	
	cout << res;

	return 0;
}

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