oj.uz

Submission #854869

# Submission time Handle Problem Language Result Execution time Memory
854869 2023-09-29T07:40:10 Z boris_mihov Passport (JOI23_passport) C++17
0 / 100
 1 ms 2512 KB 
#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;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 2392 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2512 KB Output is correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2512 KB Output is correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2512 KB Output is correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 2392 KB Output isn't correct
3 Halted 0 ms 0 KB -