Submission #1244173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244173		lovrot	Team Contest (JOI22_team)	C++20	46 / 100	1402 ms	65204 KiB

team

#include <cstdio>
#include <cassert>
#include <cstring>
#include <algorithm>
#include <vector>

#define X first
#define Y second
#define PB push_back

using namespace std;

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

const int N = 4e3 + 10;

int dvade[N][N];
vector<int> x, y, z;

void solve(vector<pair<pii, int>> v) { 
	memset(dvade, -1, sizeof(dvade));

	int n = v.size();

	for(auto &i : v) {
		x.PB(i.X.X);
		y.PB(i.X.Y);
		z.PB(i.Y);
	}

	sort(x.begin(), x.end());
	x.erase(unique(x.begin(), x.end()), x.end());
	sort(y.begin(), y.end());
	y.erase(unique(y.begin(), y.end()), y.end());
	sort(z.begin(), z.end());
	z.erase(unique(z.begin(), z.end()), z.end());

	for(auto &i : v) { 
		int a = i.X.X, b = i.X.Y, c = i.Y;
		int j = lower_bound(x.begin(), x.end(), a) - x.begin() + 1;
		int k = lower_bound(y.begin(), y.end(), b) - y.begin() + 1;

//		printf("%d %d %d %d %d\n", a, b, c, j, k);
		dvade[j][k] = max(dvade[j][k], c);
	}

	for(int i = 0; i <= n; ++i) { 
		for(int j = 0; j <= n; ++j) { 
			if(i) dvade[i][j] = max(dvade[i - 1][j], dvade[i][j]);
			if(j) dvade[i][j] = max(dvade[i][j], dvade[i][j - 1]);
//			printf("%d ", dvade[i][j]);
		}
//		printf("\n");
	}
	
	int ans = -1;
	for(auto &i : v) { 
		for(auto &j : v) { 
			int a = i.X.X, b = i.X.Y, c = i.Y;
			int a_ = j.X.X, b_ = j.X.Y, c_ = j.Y;


			int ind1 = lower_bound(x.begin(), x.end(), a) - x.begin();
			int ind2 = lower_bound(y.begin(), y.end(), b_) - y.begin();
			assert(ind1 < N && ind2 < N);
		
			if(a > a_ && b < b_ && c < dvade[ind1][ind2] && c_ < dvade[ind1][ind2] && dvade[ind1][ind2] != -1) { 
				ans = max(ans, a + b_ + dvade[ind1][ind2]);
//				printf("%d %d %d | %d %d %d | %d %d %d \n", a, b, c, a_, b_, c_, ind1, ind2, dvade[ind1][ind2]);
			}
		}
	}

	printf("%d\n", ans);
}

int main() { 
	int n;
	scanf("%d", &n);

	vector<pair<pii, int>> v;
	for(; n--; ) { 
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		v.PB({{x, y}, z});
	}

	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	assert((int) v.size() < N);

	solve(v);
	return 0;
}

Compilation message (stderr)

team.cpp: In function 'int main()':
team.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
team.cpp:85:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |                 scanf("%d%d%d", &x, &y, &z);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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