oj.uz

Submission #1092507

# Submission time Handle Problem Language Result Execution time Memory
1092507 2024-09-24T08:49:14 Z NguyenPhucThang trapezoid (balkan11_trapezoid) C++17
45 / 100
 500 ms 2964 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;
		if (a > b) swap(a, b);
		if (c > d) swap(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;
				}
			}
		}
	}

	ll maxdp = 0, cntres = 0;
	forr(i, 1, n) maxdp = max(maxdp, dp[i]);
	forr(i, 1, n) if (dp[i] == maxdp) cntres = (cntres + cnt[i]) % mod;
	cout << maxdp << " "  << cntres;
   return 0;
}

Subtask #1
45.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 11 ms 348 KB Output is correct
7 Correct 38 ms 596 KB Output is correct
8 Correct 17 ms 636 KB Output is correct
9 Correct 100 ms 604 KB Output is correct
10 Execution timed out 1002 ms 972 KB Time limit exceeded
11 Execution timed out 826 ms 1116 KB Time limit exceeded
12 Execution timed out 1043 ms 1688 KB Time limit exceeded
13 Execution timed out 1034 ms 1908 KB Time limit exceeded
14 Execution timed out 1045 ms 2144 KB Time limit exceeded
15 Execution timed out 1071 ms 2388 KB Time limit exceeded
16 Execution timed out 1046 ms 2388 KB Time limit exceeded
17 Execution timed out 1066 ms 2556 KB Time limit exceeded
18 Execution timed out 1080 ms 2644 KB Time limit exceeded
19 Execution timed out 1069 ms 2900 KB Time limit exceeded
20 Execution timed out 1061 ms 2964 KB Time limit exceeded