제출 #1086565

#제출 시각아이디문제언어결과실행 시간메모리
1086565daoquanglinh2007Passport (JOI23_passport)C++17
16 / 100
2 ms1112 KiB
#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 = 300, 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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...