제출 #908002

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
908002		12345678	사다리꼴 (balkan11_trapezoid)	C++17	45 / 100	1076 ms	5640 KiB

trapezoid

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5, mod=30013;

struct trapezoid
{
    int a=0, b=0, c=0, d=0;
    bool operator< (const trapezoid &o) const {
        return a<o.a;
    }
} s[nx];

int n, dp[nx], cnt[nx], mx, res;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>s[i].a>>s[i].b>>s[i].c>>s[i].d;
    sort(s+1, s+n+1);
    cnt[0]=1;
    for (int i=1; i<=n; i++)
    {
        for (int j=0; j<i; j++) 
        {
            if (s[i].a>s[j].b&&s[i].c>s[j].d) 
            {
                if (dp[j]+1>dp[i]) dp[i]=dp[j]+1, cnt[i]=cnt[j];
                else if (dp[j]+1==dp[i]) cnt[i]=(cnt[i]+cnt[j])%mod;
            }
        }
        mx=max(mx, dp[i]);
    }
    for (int i=1; i<=n; i++) if (dp[i]==mx) res=(res+cnt[i])%mod;
    cout<<mx<<' '<<res;
}

• Subtask 1: 45 / 100