Submission #1214048

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214048		omarrrr	Abduction 2 (JOI17_abduction2)	C++20	27 / 100	569 ms	174156 KiB

abduction2

#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pb push_back
#define mpr make_pair

const ll N=2e6 + 10 , mod=1e9 + 7, inf=1e18;

using namespace std;

ll n,m,k,q,c,x,y;
ll t[N];
ll a[N],b[N];
ll dp[2100][2100][5];

ll solve(ll i,ll j,ll d){
    if(i<0 || i>=n || j<0 || j>=m)
        return -1;
    if(dp[i][j][d]!=-1)return dp[i][j][d];

    ll x=0,y=0;
    if(d==0)
        x=1;
    else if(d==1)
        x=-1;
    else if(d==2)
        y=1;
    else
        y=-1;

    ll res=-5;
    if(d<2){
        if(a[i]>b[j]){
            res=max(solve(i,j+1,2),solve(i,j-1,3));
        }else{
            res=solve(i+x,j+y,d);
        }
    }else{
        if(b[j]>a[i])
            res=max(solve(i+1,j,0),solve(i-1,j,1));
        else
            res=solve(i+x,j+y,d);
    }


    return dp[i][j][d]=res+1;
}

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

//    freopen("dining.in","r",stdin);
//    freopen("dining.out","w",stdout);




    ll T=1;
    //cin>>T;
    while(T--){
        cin>>n>>m>>q;
        for(ll i=0;i<n;i++)
            cin>>a[i];

        for(ll i=0;i<m;i++){
            cin>>b[i];
        }
        memset(dp,-1,sizeof(dp));
        for(ll i=0;i<n;i++){
            for(ll j=0;j<m;j++){
                for(ll k=0;k<4;k++){
                    if(dp[i][j][k]==-1)
                        solve(i,j,k);
                }
            }
        }

        /*for(ll k=0;k<4;k++){
            if(dp[2][2][k]==-1)
                solve(2,2,k);
        }*/


        while(q--){
            ll x,y;
            cin>>x>>y;
            x--;y--;
            ll res=0;
            if(x)
                res=max(res,dp[x-1][y][1]+1);
            if(x+1<n)
                res=max(res,dp[x+1][y][0]+1);
            if(y)
                res=max(res,dp[x][y-1][3]+1);
            if(y+1<m)
                res=max(res,dp[x][y+1][2]+1);
            cout<<res<<"\n";
        }



    }


    return 0;
}

/*
3 3 1
3 2 6
1 4 5
3 3





*/

• Subtask 1: 13 / 13
• Subtask 2: 10 / 10
• Subtask 3: 0 / 17
• Subtask 4: 4 / 4
• Subtask 5: 0 / 56