Submission #1244147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244147		lovrot	Team Contest (JOI22_team)	C++20	0 / 100	58 ms	65204 KiB

team

#include <cstdio>
#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]);
		}
	}
	
	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(), a) - y.begin();
		
			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\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());

	solve(v);
	return 0;
}

Compilation message (stderr)

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

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