Submission #1127670

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127670		Chal1shkan	trapezoid (balkan11_trapezoid)	C++20	40 / 100	1096 ms	2240 KiB

trapezoid

# include <bits/stdc++.h>
using namespace std;
 
# define ll long long
# define ld long double
# define pii pair <int, int>
# define pll pair <ll, ll>
# define nl '\n'
# define sz(x) (int)(x).size()
# define all(x) (x).begin(), (x).end()
# define deb(x) cerr << #x << " = " << x << endl;
 
const int maxn = (int)1e5 + 3;
const ll inf = (ll)1e18 + 0;
const int mod = (int)30013;
const bool T = 0;

int n;
pii dp[maxn];

struct node {
    int a, b, c, d;
} arr[maxn];

bool cmp (node L, node R) {
    return L.a < R.a;
}

bool ok (int i, int j) {
    return arr[i].a > arr[j].b && arr[i].c > arr[j].d;
}

int add (int x, int y) {
    int res = x + y;
    if (res >= mod) res -= mod;
    return res;
}

void ma1n () {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i].a >> arr[i].b >> arr[i].c >> arr[i].d;
    }
    // sort(arr + 1, arr + 1 + n, cmp);
    for (int i = 1; i <= n; ++i) {
        dp[i].first = 1;
        dp[i].second = 1;
        for (int j = 1; j < i; ++j) {
            if (ok(i, j)) {
                if (dp[j].first + 1 == dp[i].first) {
                    dp[i].second = add(dp[i].second, dp[j].second);
                }
                else if (dp[j].first + 1 > dp[i].first) {
                    dp[i].first = dp[j].first + 1;
                    dp[i].second = dp[j].second;
                }
            }
        }
    }
    int mx = 0, var = 0;
    for (int i = 1; i <= n; ++i) {
        if (dp[i].first == mx) {
            var = add(var, dp[i].second);
        }
        else if (dp[i].first > mx) {
            mx = dp[i].first;
            var = dp[i].second;
        }
    }
    cout << mx << ' ' << var << nl;
}

signed main () {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int ttt = 1;
    if (T) cin >> ttt;
    while (ttt--) {
        ma1n();
    }
    return 0;
}

• Subtask 1: 40 / 100