제출 #1256433

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256433		nerrrmin	Passport (JOI23_passport)	C++20	16 / 100	2094 ms	29768 KiB

passport

#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
using namespace std;
const int maxn = 3e3 + 10;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int n, q;
int lt[maxn], rt[maxn];
int dp[maxn][maxn];
int main()
{
    speed();

    cin >> n;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> lt[i] >> rt[i];
    }
    cin >> q;
    int x;
    cin >> x;

    for (int i = 1; i <= n; ++ i)
    {
        for (int j = 1; j <= n; ++ j)
            dp[i][j] = 1e9;
    }
    dp[lt[x]][rt[x]] = 1;
    for (int sz = 1; sz <= n; ++ sz)
    {
        for (int i = 1; i <= n; ++ i)
        {
            int j = i + sz - 1;
            if(j > n)break;
            if(dp[i][j] == 1e9)continue;
            //cout << i << " " << j << " is " << dp[i][j] << endl;
            for (int k = 1; k <= n; ++ k)
            {
                if(k >= i && k <= j)
                {
                    int newl = min(i, lt[k]);
                int newr = max(j, rt[k]);
                dp[newl][newr] = min(dp[i][j] + 1, dp[newl][newr]);
                }
            }

        }
    }
    if(dp[1][n] == 1e9)cout << -1 << endl;
    else cout << dp[1][n] << endl;
    return 0;
}

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