oj.uz

Submission #853236

# Submission time Handle Problem Language Result Execution time Memory
853236 2023-09-23T17:22:35 Z sofijavelkovska trapezoid (balkan11_trapezoid) C++14
50 / 100
 500 ms 5708 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN=100000;
const int MOD=30013;

int a[MAXN], b[MAXN], c[MAXN], d[MAXN];

bool compare(int x, int y)
{
    return b[x]<b[y];
}

bool intersect(int x, int y)
{
    if (b[x]>a[y])
        return true;
    if (d[x]>c[y])
        return true;

    return false;
}

int main()
{
    int n, maxcardinality, totalways=0, i, j;
    cin >> n;
    int sorted[n], dpmax[n], dpcount[n];
    for (i=0; i<n; i++)
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    for (i=0; i<n; i++)
        sorted[i]=i;
    sort(sorted, sorted+n, compare);
    for (i=0; i<n; i++)
    {
        dpmax[i]=1;
        dpcount[i]=1;
        for (j=0; j<i; j++)
        {
            if (!intersect(sorted[j], sorted[i]))
            {
                if (dpmax[j]+1>dpmax[i])
                {
                    dpmax[i]=dpmax[j]+1;
                    dpcount[i]=dpcount[j];
                }
                else if (dpmax[j]+1==dpmax[i])
                    dpcount[i]=(dpcount[i]+dpcount[j])%30013;
            }
        }
    }
    maxcardinality=*max_element(dpmax, dpmax+n);
    for (i=0; i<n; i++)
        if (dpmax[i]==maxcardinality)
            totalways=(totalways+dpcount[i])%MOD;
    cout << maxcardinality << " " << totalways;

    return 0;
}

Subtask #1
50.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 448 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 6 ms 348 KB Output is correct
6 Correct 14 ms 596 KB Output is correct
7 Correct 20 ms 1112 KB Output is correct
8 Correct 18 ms 600 KB Output is correct
9 Correct 105 ms 932 KB Output is correct
10 Correct 384 ms 1372 KB Output is correct
11 Execution timed out 881 ms 2040 KB Time limit exceeded
12 Execution timed out 1045 ms 3144 KB Time limit exceeded
13 Execution timed out 1020 ms 3412 KB Time limit exceeded
14 Execution timed out 1047 ms 4260 KB Time limit exceeded
15 Execution timed out 1025 ms 4352 KB Time limit exceeded
16 Execution timed out 1028 ms 4688 KB Time limit exceeded
17 Execution timed out 1045 ms 4848 KB Time limit exceeded
18 Execution timed out 1028 ms 5200 KB Time limit exceeded
19 Execution timed out 1050 ms 5460 KB Time limit exceeded
20 Execution timed out 1034 ms 5708 KB Time limit exceeded