oj.uz

Submission #804664

# Submission time Handle Problem Language Result Execution time Memory
804664 2023-08-03T10:45:14 Z thimote75 Passport (JOI23_passport) C++14
16 / 100
 2000 ms 53964 KB 
#include <bits/stdc++.h>

using namespace std;

using di = pair<int, int>;
using vd = vector<di>;

vd dis;

const int MAXN = 2600;
int dp[MAXN][MAXN];

int _compute (int l, int r) {
    if (l == 0 && r == dis.size() - 1) return 0;
    if (dp[l][r] != -1) return dp[l][r];

    dp[l][r] = 1e9;
    for (int i = l; i <= r; i ++) {
        dp[l][r] = min(
            dp[l][r],
            _compute(min(l, dis[i].first), max(r, dis[i].second)) + 1
        );
    }

    return dp[l][r];
}
int compute (int l, int r) {
    return _compute(l, r) >= 1e9 ? -1 : _compute(l, r);
}

int main () {
    int N;
    cin >> N;

    for (int i = 0; i < N; i ++)
        for (int j = 0; j < N; j ++)
            dp[i][j] = -1;

    dis = vd(N);

    for (int i = 0; i < N; i ++) {
        int l, r;
        cin >> l >> r;
        l --;
        r --;

        dis[i] = { l, r };
    }

    int Q; cin >> Q;
    for (int i = 0; i < Q; i ++) {
        int x; cin >> x;
        x --;

        cout << compute(x, x) << "\n";
    }
}

Compilation message

passport.cpp: In function 'int _compute(int, int)':
passport.cpp:15:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     if (l == 0 && r == dis.size() - 1) return 0;
      |                   ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 316 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Runtime error 75 ms 53964 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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 3 ms 1748 KB Output is correct
12 Correct 5 ms 1748 KB Output is correct
13 Correct 1 ms 1748 KB Output is correct
14 Correct 2 ms 1788 KB Output is correct
15 Correct 6 ms 1876 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 3 ms 1748 KB Output is correct
12 Correct 5 ms 1748 KB Output is correct
13 Correct 1 ms 1748 KB Output is correct
14 Correct 2 ms 1788 KB Output is correct
15 Correct 6 ms 1876 KB Output is correct
16 Execution timed out 2074 ms 24020 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 3 ms 1748 KB Output is correct
12 Correct 5 ms 1748 KB Output is correct
13 Correct 1 ms 1748 KB Output is correct
14 Correct 2 ms 1788 KB Output is correct
15 Correct 6 ms 1876 KB Output is correct
16 Execution timed out 2074 ms 24020 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

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