oj.uz

Submission #889316

# Submission time Handle Problem Language Result Execution time Memory
889316 2023-12-19T10:48:50 Z borisAngelov trapezoid (balkan11_trapezoid) C++17
15 / 100
 500 ms 5520 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;
const int mod = 30013;

int n;

struct Segment
{
    int x;
    int y;
};

bool cross(const Segment& fr, const Segment& sc)
{
    return fr.x <= sc.y && fr.y >= sc.x;
}

struct Trapezoid
{
    Segment up;
    Segment down;
};

Trapezoid a[maxn];

pair<int, int> dp[maxn];

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n;

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i].up.x >> a[i].up.y >> a[i].down.x >> a[i].down.y;
    }

    for (int i = 1; i <= n; ++i)
    {
        dp[i].first = 1;
        dp[i].second = 1;

        for (int j = i - 1; j >= 1; --j)
        {
            if (cross(a[i].down, a[j].down) == false && cross(a[i].up, a[j].up) == false && !((a[i].down.y < a[j].down.x && a[i].up.x > a[j].up.y) || (a[i].down.x > a[j].down.y && a[j].up.x > a[i].up.y)))
            {
                //cout << i << ' ' << j << endl;

                if (dp[i].first < 1 + dp[j].first)
                {
                    dp[i].first = 1 + dp[j].first;
                    dp[i].second = dp[j].second;
                }
                else if (dp[i].first == 1 + dp[j].first)
                {
                    dp[i].second += dp[j].second;

                    if (dp[i].second >= mod)
                    {
                        dp[i].second -= mod;
                    }
                }
            }
        }
    }

    int mx = 0;
    int cnt = 0;

    for (int i = 1; i <= n; ++i)
    {
        if (mx < dp[i].first)
        {
            mx = dp[i].first;
            cnt = dp[i].second;
        }
        else if (mx == dp[i].first)
        {
            cnt += dp[i].second;

            if (cnt >= mod)
            {
                cnt -= mod;
            }
        }
    }

    cout << mx << ' ' << cnt << endl;

    return 0;
}

Subtask #1
15.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Incorrect 2 ms 2396 KB Output isn't correct
5 Incorrect 5 ms 2560 KB Output isn't correct
6 Incorrect 9 ms 2524 KB Output isn't correct
7 Incorrect 15 ms 2632 KB Output isn't correct
8 Correct 29 ms 2652 KB Output is correct
9 Incorrect 93 ms 2652 KB Output isn't correct
10 Incorrect 382 ms 3176 KB Output isn't correct
11 Execution timed out 573 ms 3408 KB Time limit exceeded
12 Execution timed out 1036 ms 3908 KB Time limit exceeded
13 Execution timed out 1034 ms 4088 KB Time limit exceeded
14 Execution timed out 1043 ms 4832 KB Time limit exceeded
15 Execution timed out 1025 ms 4752 KB Time limit exceeded
16 Execution timed out 1022 ms 4696 KB Time limit exceeded
17 Execution timed out 1037 ms 4828 KB Time limit exceeded
18 Execution timed out 1004 ms 5080 KB Time limit exceeded
19 Execution timed out 1040 ms 5340 KB Time limit exceeded
20 Execution timed out 1068 ms 5520 KB Time limit exceeded