oj.uz

Submission #854870

# Submission time Handle Problem Language Result Execution time Memory
854870 2023-09-29T07:43:08 Z boris_mihov Passport (JOI23_passport) C++17
16 / 100
 2000 ms 25180 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()
{
    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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Runtime error 2 ms 472 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2532 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 4 ms 4952 KB Output is correct
12 Correct 2 ms 4700 KB Output is correct
13 Correct 1 ms 4700 KB Output is correct
14 Correct 1 ms 4700 KB Output is correct
15 Correct 3 ms 4956 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2532 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 4 ms 4952 KB Output is correct
12 Correct 2 ms 4700 KB Output is correct
13 Correct 1 ms 4700 KB Output is correct
14 Correct 1 ms 4700 KB Output is correct
15 Correct 3 ms 4956 KB Output is correct
16 Correct 1504 ms 19780 KB Output is correct
17 Correct 651 ms 22512 KB Output is correct
18 Correct 14 ms 17756 KB Output is correct
19 Correct 24 ms 17456 KB Output is correct
20 Execution timed out 2086 ms 25180 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2532 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 4 ms 4952 KB Output is correct
12 Correct 2 ms 4700 KB Output is correct
13 Correct 1 ms 4700 KB Output is correct
14 Correct 1 ms 4700 KB Output is correct
15 Correct 3 ms 4956 KB Output is correct
16 Correct 1504 ms 19780 KB Output is correct
17 Correct 651 ms 22512 KB Output is correct
18 Correct 14 ms 17756 KB Output is correct
19 Correct 24 ms 17456 KB Output is correct
20 Execution timed out 2086 ms 25180 KB Time limit exceeded
21 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 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Runtime error 2 ms 472 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -