Submission #854870

#	Time	Username	Problem	Language	Result	Execution time	Memory
854870		boris_mihov	Passport (JOI23_passport)	C++17	16 / 100	2086 ms	25180 KiB

passport

#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()
{
    int res = f(from, from);
    if (res == INF) res = -1;
    std::cout << res << '\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;
}

• Subtask 1: 0 / 6
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 8
• Subtask 5: 0 / 46