Submission #726093

#	Time	Username	Problem	Language	Result	Execution time	Memory
726093		Jovica	trapezoid (balkan11_trapezoid)	C++14	14 / 100	1087 ms	6568 KiB

trapezoid

#include <bits/stdc++.h>

using namespace std;
long long n;
vector<tuple<long long,long long,long long,long long> > v;
bool visited[100000];
pair<long long,long long> dp[100000];

/// zima,nacini
pair<long long,long long> f(long long poz)
{
    //cout <<"ulava u "<<poz<<endl;
    if (poz==v.size()) return {0,0};
    if (visited[poz]==true) return dp[poz];

    long long  zima=0,nacini=1;
    pair<long long,long long> p={zima,nacini};
    for (int i=0;i<n;i++)
    {
        if (get<1>(v[poz])<get<0>(v[i]) && get<3>(v[poz])<get<2>(v[i]))
        {
            //cout<<"poz = "<<poz<<" && i = "<<i<<"   "<< get<1>(v[poz])<<" < "<<get<0>(v[i])<<" && "<<get<3>(v[poz])<<" < "<<get<2>(v[i])<<endl;
            p=f(i);
            if (p.first==zima) nacini+=p.second;
            else if(p.first>zima)
            {
                zima=p.first;
                nacini=p.second;
            }
        }
    }

    zima++;
    p={zima,nacini};
    visited[poz]=true;
    dp[poz]=p;
    return p;
}

int main()
{
    cin>>n;
    for (long long i=0;i<n;i++)
    {
        long long A,B,C,D;
        cin>>A>>B>>C>>D;
        v.push_back({A,B,C,D});
    }

    //sort(v.begin(),v.end());
    pair<long long,long long> p={0,0};
    for (long long i=0;i<n;i++)
        if (visited[i]==false)
        {
            pair<long long,long long> q=f(i);
            //cout<< "i="<<i<<" zima="<<q.first<<endl<<" najde="<<q.second<<endl;
            if (p.first==q.first) p.second+=q.second;
            if (q.first>p.first) p=q;
        }

    //for (int i=1;i<n;i++) if (dp[i].second==p.first) p.second+=dp[i].second;

    cout<<p.first<<" "<<p.second<<endl;
    return 0;
}

Compilation message (stderr)

trapezoid.cpp: In function 'std::pair<long long int, long long int> f(long long int)':
trapezoid.cpp:13:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::tuple<long long int, long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     if (poz==v.size()) return {0,0};
      |         ~~~^~~~~~~~~~

• Subtask 1: 14 / 100