oj.uz

Submission #726104

# Submission time Handle Problem Language Result Execution time Memory
726104 2023-04-18T13:22:21 Z Jovica trapezoid (balkan11_trapezoid) C++14
24 / 100
 500 ms 2492 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 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Partially correct 2 ms 212 KB Partially correct
4 Partially correct 4 ms 340 KB Partially correct
5 Partially correct 16 ms 388 KB Partially correct
6 Partially correct 38 ms 448 KB Partially correct
7 Partially correct 55 ms 464 KB Partially correct
8 Partially correct 52 ms 560 KB Partially correct
9 Partially correct 264 ms 788 KB Partially correct
10 Execution timed out 1073 ms 976 KB Time limit exceeded
11 Execution timed out 1065 ms 1024 KB Time limit exceeded
12 Execution timed out 1039 ms 1452 KB Time limit exceeded
13 Execution timed out 1053 ms 1484 KB Time limit exceeded
14 Execution timed out 1052 ms 2452 KB Time limit exceeded
15 Execution timed out 1076 ms 2468 KB Time limit exceeded
16 Execution timed out 1033 ms 2456 KB Time limit exceeded
17 Execution timed out 1080 ms 2460 KB Time limit exceeded
18 Execution timed out 1064 ms 2492 KB Time limit exceeded
19 Execution timed out 1041 ms 2368 KB Time limit exceeded
20 Execution timed out 1060 ms 2444 KB Time limit exceeded