Submission #1053629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053629		MinhBoss	trapezoid (balkan11_trapezoid)	C++17	10 / 100	20 ms	1160 KiB

trapezoid

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second
#define endl '\n'
#define pb push_back

struct TrapeZoid{
    ll uL, uR, dR, dL;
    TrapeZoid(ll _uL=0, ll _uR=0, ll _dL=0, ll _dR=0){
        uL = _uL;
        uR = _uR;
        dR = _dR;
        dL = _dL;
    }
};

const ll MAX = 5e3;
ll n;
TrapeZoid a[MAX];
pair<ll,ll> dp[MAX];

bool intersect(ll i, ll j){
    if(a[i].uL > a[j].uR || a[i].uR < a[j].uL){
        if(a[i].dL > a[j].dR || a[i].dR < a[j].dL) return false;
    }
    return true;
}

int main(){
    cin>>n;
    for(int i =1;i<=n;i++){
        ll x,y,z,d; cin>>x>>y>>z>>d;
        a[i] = TrapeZoid(x,y,z,d);
    }
    for(int i =1;i<=n;i++){
        dp[i] = {1,1};
        for(int j = i-1; j>=1; j--){
            if(!intersect(i,j)){
                if(dp[i].fi == dp[j].fi + 1) dp[i].se += dp[j].se;
                else if(dp[i].fi < dp[j].fi + 1){
                    dp[i] = {dp[j].fi+1, dp[j].se};
                }
            }
        }

    }
    ll res=0, mx=0;
    for(int i =1;i<=n;i++){
        mx = max(mx, dp[i].fi);
    }
    for(int i =1;i<=n;i++){
        if(dp[i].fi == mx) res += dp[i].se;
    }
    cout<<mx<<" "<<res;

}

• Subtask 1: 10 / 100