oj.uz

Submission #144258

# Submission time Handle Problem Language Result Execution time Memory
144258 2019-08-16T11:56:47 Z Sorting trapezoid (balkan11_trapezoid) C++14
26 / 100
 500 ms 4940 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Partially correct 3 ms 376 KB Partially correct
4 Partially correct 4 ms 376 KB Partially correct
5 Partially correct 7 ms 504 KB Partially correct
6 Partially correct 13 ms 504 KB Partially correct
7 Partially correct 20 ms 504 KB Partially correct
8 Partially correct 24 ms 632 KB Partially correct
9 Partially correct 171 ms 860 KB Partially correct
10 Partially correct 390 ms 1528 KB Partially correct
11 Execution timed out 891 ms 1872 KB Time limit exceeded
12 Execution timed out 1070 ms 2848 KB Time limit exceeded
13 Execution timed out 1075 ms 3260 KB Time limit exceeded
14 Execution timed out 1083 ms 3792 KB Time limit exceeded
15 Execution timed out 1073 ms 4092 KB Time limit exceeded
16 Execution timed out 1079 ms 4088 KB Time limit exceeded
17 Execution timed out 1071 ms 4392 KB Time limit exceeded
18 Execution timed out 1074 ms 4728 KB Time limit exceeded
19 Execution timed out 1080 ms 4856 KB Time limit exceeded
20 Execution timed out 1048 ms 4940 KB Time limit exceeded