제출 #854869

#제출 시각아이디문제언어결과실행 시간메모리
854869boris_mihovPassport (JOI23_passport)C++17
0 / 100
1 ms2512 KiB
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 2500 + 10;
const int INF  = 1e9;

int n;
int l[MAXN];
int r[MAXN];
int dp[MAXN][MAXN];
bool bl[MAXN][MAXN];
int from;

int f(int left, int right)
{
    if (left == 1 && right == n)
    {
        return 0;
    }

    if (bl[left][right])
    {
        return dp[left][right];
    }

    bl[left][right] = true;
    dp[left][right] = INF;

    for (int i = left ; i <= right ; ++i)
    {
        if (l[i] < left)
        {
            dp[left][right] = std::min(dp[left][right], f(l[i], std::max(r[i], right)) + 1);
        }

        if (r[i] > right)
        {
            dp[left][right] = std::min(dp[left][right], f(std::min(l[i], left), r[i]) + 1);
        }
    }

    return dp[left][right];
}

void solve()
{
    std::cout << f(from, from) << '\n';
}  

void input()
{
    std::cin >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> l[i] >> r[i];
    }

    std::cin >> from >> from;
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...