oj.uz

답안 #726101

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
726101 2023-04-18T13:21:51 Z Jovica 사다리꼴 (balkan11_trapezoid) C++14
14 / 100
 500 ms 4536 KB 
#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

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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 2 ms 340 KB Expected int32, but "10313130667392" found
4 Incorrect 4 ms 340 KB Expected int32, but "-8550276992825950208" found
5 Partially correct 17 ms 468 KB Partially correct
6 Incorrect 28 ms 468 KB Expected int32, but "-8629080777422869056" found
7 Incorrect 52 ms 612 KB Expected int32, but "-3319866744691032064" found
8 Partially correct 56 ms 684 KB Partially correct
9 Incorrect 282 ms 916 KB Expected int32, but "2248786528710863832" found
10 Execution timed out 1063 ms 1404 KB Time limit exceeded
11 Execution timed out 1036 ms 1632 KB Time limit exceeded
12 Execution timed out 1075 ms 2440 KB Time limit exceeded
13 Execution timed out 1081 ms 2632 KB Time limit exceeded
14 Execution timed out 1081 ms 4496 KB Time limit exceeded
15 Execution timed out 1081 ms 4536 KB Time limit exceeded
16 Execution timed out 1039 ms 4532 KB Time limit exceeded
17 Execution timed out 1075 ms 4408 KB Time limit exceeded
18 Execution timed out 1077 ms 4492 KB Time limit exceeded
19 Execution timed out 1047 ms 4528 KB Time limit exceeded
20 Execution timed out 1076 ms 4480 KB Time limit exceeded