Submission #1142930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142930		VMaksimoski008	Passport (JOI23_passport)	C++17	16 / 100	2095 ms	1114112 KiB

passport

#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const ll inf = 1e18;
const int maxn = 1e5 + 5;

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

    int n; cin >> n;
    vector<int> L(n+1), R(n+1);
    for(int i=1; i<=n; i++) cin >> L[i] >> R[i];

    int q; cin >> q;
    while(q--) {
        int x; cin >> x;
        int dp[n+1][n+1];
        for(int i=1; i<=n; i++)
            for(int j=i; j<=n; j++) dp[i][j] = 1e9;

        dp[L[x]][R[x]] = 1;
        for(int l=1; l<=n; l++) {
            for(int i=1,j=l; j<=n; i++, j++) {
                for(int k=i; k<=j; k++) {
                    int ni = min(i, L[k]);
                    int nj = max(j, R[k]);
                    dp[ni][nj] = min(dp[ni][nj], dp[i][j] + 1);
                }
            }
        }

        cout << (dp[1][n] == 1e9 ? -1 : dp[1][n]) << '\n';
    }
}

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