Submission #1086566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086566		daoquanglinh2007	Passport (JOI23_passport)	C++17	40 / 100	2077 ms	31172 KiB

passport

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair
#define isz(a) (int)(a).size()

const int NM = 2500, inf = 1e9+7;

int ntest = 1;
int N, L[NM+5], R[NM+5], Q, dp[NM+5][NM+5];

void solve(){
    cin >> N;
    for (int i = 1; i <= N; i++)
        cin >> L[i] >> R[i];
    cin >> Q;
    while (Q--){
        int X; cin >> X;
        for (int i = 1; i <= N; i++)
            for (int j = i; j <= N; j++) dp[i][j] = +inf;
        dp[X][X] = 0;
        for (int i = N; i >= 1; i--)
            for (int j = i; j <= N; j++){
                if (dp[i][j] == +inf) continue;
                for (int k = i; k <= j; k++)
                    if (L[k] < i || R[k] > j) dp[min(i, L[k])][max(j, R[k])] = min(dp[min(i, L[k])][max(j, R[k])], dp[i][j]+1);
            }
        cout << (dp[1][N] == +inf ? -1 : dp[1][N]) << '\n';
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    //cin >> ntest;
    while (ntest--){
        solve();
    }

#ifdef daoquanglinh2007
    cout << '\n';
    for (int i = 1; i <= 100; i++) cout << '=';
    cout << "\nExecution time: " << 1*(clock()) << " ms\n";
#endif
    return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 0 / 8
• Subtask 5: 0 / 46