Submission #1287164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287164		denislav	Passport (JOI23_passport)	C++20	40 / 100	2096 ms	14500 KiB

passport

# include <iostream>
using namespace std;

const int MAX=3e3+11;

int n,q;
pair<int,int> a[MAX];

int dp[MAX][MAX];

int rec(int l, int r)
{
    if(l==1 and r==n) return 0;
    if(dp[l][r]!=0) return dp[l][r];

    int ans=1e9,lm=l,rm=r;
    for(int i=l;i<=r;i++)
    {
        int l2=min(a[i].first,l);
        int r2=max(a[i].second,r);
        if(!(l2==l and r2==r)) ans=min(ans,rec(l2,r2)+1);
        lm=min(lm,a[i].first);
        rm=max(rm,a[i].second);
    }
    if(!(lm==l and rm==r)) ans=min(ans,rec(lm,rm)+2);

    dp[l][r]=ans;
    return ans;
}

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

    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].first>>a[i].second;

    cin>>q;
    while(q--)
    {
        int pos;
        cin>>pos;
        int ans=rec(a[pos].first,a[pos].second);
        if(ans==1e9) cout<<-1<<"\n";
        else cout<<ans+1<<"\n";
    }

    return 0;
}

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