Submission #145502

#	Time	Username	Problem	Language	Result	Execution time	Memory
145502		MKopchev	trapezoid (balkan11_trapezoid)	C++14	45 / 100	1087 ms	5368 KiB

trapezoid

#include<bits/stdc++.h>
using namespace std;
const int nmax=2e5+42,mod=30013;
struct rect
{
    int a,b,c,d;
};
bool cmp(rect a,rect b)
{
    return a.b<b.b;
}
int n;
rect inp[nmax];
pair<int/*maximum*/,int/*times*/> dp[nmax];
int main()
{
    scanf("%i",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%i%i%i%i",&inp[i].a,&inp[i].b,&inp[i].c,&inp[i].d);
        dp[i]={1,1};
    }
    sort(inp+1,inp+n+1,cmp);

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        if(inp[j].b<inp[i].a&&inp[j].d<inp[i].c)
        {
            pair<int/*maximum*/,int/*times*/> now=dp[j];
            now.first++;
            if(dp[i].first<now.first)dp[i]=now;
            else if(dp[i].first==now.first)dp[i].second=(dp[i].second+now.second)%mod;
        }

    }
    int maxi=0,sum=0;
    for(int i=1;i<=n;i++)
    {
        if(dp[i].first>maxi)
        {
            maxi=dp[i].first;
            sum=dp[i].second;
        }
        else if(dp[i].first==maxi)
        {
            sum=(sum+dp[i].second)%mod;
        }
    }

    printf("%i %i\n",maxi,sum);
    return 0;
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
trapezoid.cpp:20:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i%i%i",&inp[i].a,&inp[i].b,&inp[i].c,&inp[i].d);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 45 / 100