Submission #725688

#	Time	Username	Problem	Language	Result	Execution time	Memory
725688		Jovica	trapezoid (balkan11_trapezoid)	C++14	10 / 100	1091 ms	12796 KiB

trapezoid

#include <bits/stdc++.h>

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

/// zima,nacini
pair<int,int> f(int poz)
{
    if (poz==v.size()) return {0,0};
    if (visited[poz]==true) return dp[poz];

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

    zima++;
    if (poz==0)
    for (int i=poz+1;i<n;i++)
    {
        if (get<1>(v[poz])>=get<0>(v[i]) || get<3>(v[poz])>=get<2>(v[i]))
        {
            p=f(i);
            if (zima==p.first) nacini+=p.second;
        }
    }

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

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

    sort(v.begin(),v.end());
    pair<int,int> p= f(0);
    cout<<p.first<<" "<<p.second<<endl;
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 10 / 100