Submission #768598

#	Time	Username	Problem	Language	Result	Execution time	Memory
768598		danikoynov	Passport (JOI23_passport)	C++14	48 / 100	1723 ms	20712 KiB

passport

#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 (stderr)

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
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 0 / 46