oj.uz

Submission #725697

# Submission time Handle Problem Language Result Execution time Memory
725697 2023-04-17T22:16:12 Z Jovica trapezoid (balkan11_trapezoid) C++14
24 / 100
 500 ms 2776 KB 
#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)
{
    //cout <<"ulava u "<<poz<<endl;
    if (poz==v.size()) return {0,0};
    if (visited[poz]==true) return dp[poz];

    int  zima=0,nacini=1;
    pair<int,int> 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 (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={0,0};
    for (int i=0;i<n;i++)
        if (visited[i]==false)
        {
            pair<int,int> 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

trapezoid.cpp: In function 'std::pair<int, int> f(int)':
trapezoid.cpp:13: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]
   13 |     if (poz==v.size()) return {0,0};
      |         ~~~^~~~~~~~~~

Subtask #1
24.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Partially correct 2 ms 340 KB Partially correct
4 Partially correct 4 ms 368 KB Partially correct
5 Partially correct 12 ms 320 KB Partially correct
6 Partially correct 25 ms 516 KB Partially correct
7 Partially correct 47 ms 552 KB Partially correct
8 Partially correct 48 ms 596 KB Partially correct
9 Partially correct 259 ms 912 KB Partially correct
10 Execution timed out 1063 ms 1356 KB Time limit exceeded
11 Execution timed out 1067 ms 1324 KB Time limit exceeded
12 Execution timed out 1080 ms 1712 KB Time limit exceeded
13 Execution timed out 1086 ms 1892 KB Time limit exceeded
14 Execution timed out 1080 ms 2696 KB Time limit exceeded
15 Execution timed out 1068 ms 2680 KB Time limit exceeded
16 Execution timed out 1069 ms 2624 KB Time limit exceeded
17 Execution timed out 1070 ms 2640 KB Time limit exceeded
18 Execution timed out 1075 ms 2672 KB Time limit exceeded
19 Execution timed out 1085 ms 2776 KB Time limit exceeded
20 Execution timed out 1066 ms 2620 KB Time limit exceeded