Submission #144258

#	Time	Username	Problem	Language	Result	Execution time	Memory
144258		Sorting	trapezoid (balkan11_trapezoid)	C++14	26 / 100	1083 ms	4940 KiB

trapezoid

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 7;
const int mod = 30013;
const int inf = 1e9;

struct trap{
	int a, b, c, d;

	trap(){}
	trap(int a, int b, int c, int d){
		this -> a = a;
		this -> b = b;
		this -> c = c;
		this -> d = d;
	}
};

bool cmp(trap lvalue, trap rvalue){
	return lvalue.a < rvalue.a;
}

pair<int, int> dp[MAXN];
trap t[MAXN];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n;

	cin >> n;

	t[0] = trap(-inf, -inf + 1, -inf, -inf + 1);

	for(int i = 1; i <= n; ++i){
		cin >> t[i].a >> t[i].b >> t[i].c >> t[i].d;
	}

	sort(t, t + n + 1, cmp);

	for(int i = n; i >= 0; --i){
		dp[i] = {1, 1};
		for(int j = i + 1; j <= n; ++j){
			if(t[j].a > t[i].b && t[j].c > t[i].d){
				if(dp[j].first + 1 > dp[i].first){
					dp[i].first = dp[j].first + 1;
					dp[i].second = dp[j].second;
				}
				else{
					if(dp[j].first + 1 == dp[i].first){
						dp[i].second += dp[j].second;
					}
				}
			}
		}
	}

	cout << dp[0].first - 1 << " " << dp[0].second << "\n";

	return 0;
}

• Subtask 1: 26 / 100