oj.uz

Submission #768598

# Submission time Handle Problem Language Result Execution time Memory
768598 2023-06-28T09:43:04 Z danikoynov Passport (JOI23_passport) C++14
48 / 100
 1723 ms 20712 KB 
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 2.5e3 + 10;

int n, q, l[maxn], r[maxn];
int dp[maxn][maxn];
int rec(int i, int j)
{

    if (i == 1 && j == n)
        return 0;

        if (dp[i][j] != 0)
            return dp[i][j];
        int ans = 1e9;
    for (int pos = i; pos <= j; pos ++)
    {
        if (l[pos] >= i && r[pos] <= j)
            continue;
        ans = min(ans, 1 + rec(min(i, l[pos]), max(j, r[pos])));
    }
    return (dp[i][j] = ans);
}
void action(int x)
{

        int ans = rec(x, x);
        if (ans > n)
        cout << -1 << endl;
        else
            cout << ans << endl;
}
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> l[i] >> r[i];

    cin >> q;
    for (int i = 1; i <= q; i ++)
    {
        int x;
        cin >> x;
        action(x);
    }

}

int main()
{
    speed();
    solve();
    return 0;
}

Compilation message

passport.cpp: In function 'int rec(int, int)':
passport.cpp:21:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   21 |     if (i == 1 && j == n)
      |     ^~
passport.cpp:24:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   24 |         if (dp[i][j] != 0)
      |         ^~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Runtime error 2 ms 600 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 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 1 ms 752 KB Output is correct
14 Correct 1 ms 844 KB Output is correct
15 Correct 2 ms 968 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 1 ms 752 KB Output is correct
14 Correct 1 ms 844 KB Output is correct
15 Correct 2 ms 968 KB Output is correct
16 Correct 1077 ms 6516 KB Output is correct
17 Correct 444 ms 7496 KB Output is correct
18 Correct 10 ms 5080 KB Output is correct
19 Correct 17 ms 4700 KB Output is correct
20 Correct 1077 ms 12692 KB Output is correct
21 Correct 478 ms 7124 KB Output is correct
22 Correct 1 ms 372 KB Output is correct
23 Correct 1160 ms 7312 KB Output is correct
24 Correct 557 ms 3296 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 1 ms 752 KB Output is correct
14 Correct 1 ms 844 KB Output is correct
15 Correct 2 ms 968 KB Output is correct
16 Correct 1077 ms 6516 KB Output is correct
17 Correct 444 ms 7496 KB Output is correct
18 Correct 10 ms 5080 KB Output is correct
19 Correct 17 ms 4700 KB Output is correct
20 Correct 1077 ms 12692 KB Output is correct
21 Correct 478 ms 7124 KB Output is correct
22 Correct 1 ms 372 KB Output is correct
23 Correct 1160 ms 7312 KB Output is correct
24 Correct 557 ms 3296 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 1520 ms 15532 KB Output is correct
28 Correct 867 ms 16876 KB Output is correct
29 Correct 1723 ms 20712 KB Output is correct
30 Correct 582 ms 15812 KB Output is correct
31 Correct 10 ms 12560 KB Output is correct

Subtask #5
0 / 46.0

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