oj.uz

Submission #1092506

# Submission time Handle Problem Language Result Execution time Memory
1092506 2024-09-24T08:43:12 Z NguyenPhucThang trapezoid (balkan11_trapezoid) C++14
18 / 100
 500 ms 5712 KB 
#include <bits/stdc++.h>
#define forr(i, a, b) for (int i = (a); i <= (b); i++)
#define ford(i, a, b) for (int i = (a); i >= (b); i--)
#define forf(i, a, b) for (int i = (a); i < (b); i++)
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vii vector<pii>
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

using namespace std;
const int base = 31;
const ll mod = 30013;
const ll oo = 1e18;
const int N = 1e6 + 5;

ll dp[N], cnt[N];
struct trapezoid{
	int a, b, c, d;

	bool operator < (const trapezoid &other){
		return min(a, c) < min(other.a, other.c);
	}
} trape[N];


int main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);
  
	int n;
	cin >> n;
	forr(i, 1, n) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		trape[i] = {a, b, c, d};
	}

	sort(trape + 1, trape + n + 1);

	forr(i, 1, n) cnt[i] = 1;

	forr(i, 1, n){
		dp[i] = 1;
		forr(j, 1, i - 1){
			if (trape[j].b < trape[i].a && trape[j].d < trape[i].c){
				if (dp[j] + 1 > dp[i]) {
					dp[i] = dp[j] + 1;
					cnt[i] = cnt[j];
				}
				else if (dp[j] + 1 == dp[i]){
					cnt[i] += cnt[j];
					cnt[i] %= mod;
				}
			}
		}
	}

	int res1 = 0, res2 = 0;
	forr(i, 1, n){
		if (res1 < dp[i]) res1 = dp[i], res2 = cnt[i];
	}
	cout << res1 << " " << res2;
   return 0;
}

Subtask #1
18.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 KB Partially correct
2 Partially correct 0 ms 348 KB Partially correct
3 Partially correct 1 ms 348 KB Partially correct
4 Partially correct 3 ms 428 KB Partially correct
5 Partially correct 5 ms 348 KB Partially correct
6 Partially correct 11 ms 632 KB Partially correct
7 Partially correct 38 ms 604 KB Partially correct
8 Partially correct 17 ms 600 KB Partially correct
9 Partially correct 102 ms 984 KB Partially correct
10 Execution timed out 1004 ms 1504 KB Time limit exceeded
11 Execution timed out 823 ms 1876 KB Time limit exceeded
12 Execution timed out 1041 ms 3024 KB Time limit exceeded
13 Execution timed out 1050 ms 3628 KB Time limit exceeded
14 Execution timed out 1022 ms 4184 KB Time limit exceeded
15 Execution timed out 1030 ms 4184 KB Time limit exceeded
16 Execution timed out 1043 ms 4440 KB Time limit exceeded
17 Execution timed out 1020 ms 4944 KB Time limit exceeded
18 Execution timed out 1033 ms 5060 KB Time limit exceeded
19 Execution timed out 1045 ms 5460 KB Time limit exceeded
20 Execution timed out 1035 ms 5712 KB Time limit exceeded