Submission #853236

#	Time	Username	Problem	Language	Result	Execution time	Memory
853236		sofijavelkovska	trapezoid (balkan11_trapezoid)	C++14	50 / 100	1050 ms	5708 KiB

trapezoid

#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 / 100