Submission #1213467

#TimeUsernameProblemLanguageResultExecution timeMemory
1213467omarrrrAbduction 2 (JOI17_abduction2)C++20
0 / 100
960 ms104580 KiB
#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][3]; ll solve(ll i,ll j,ll d,ll x=0,ll y=0){ if(i<0 || i>=n || j<0 || j>=m) return -1; if(dp[i][j][d]!=-1)return dp[i][j][d]; if(d==4){ dp[i][j][d]=max(solve(i-1,j,0,-1,0),max(solve(i+1,j,1,1,0),max(solve(i,j-1,2,0,-1),solve(i,j+1,3,0,1)))); }else if(d==0 || d==1){ if(a[i]>b[j]){ dp[i][j][d]=max(solve(i,j-1,2,0,-1),solve(i,j+1,3,0,1)); }else{ dp[i][j][d]=solve(i+x,j+y,d,x,y); } }else{ if(a[i]<b[j]){ dp[i][j][d]=max(solve(i-1,j,0,-1,0),solve(i+1,j,1,1,0)); }else{ dp[i][j][d]=solve(i+x,j+y,d,x,y); } } return dp[i][j][d]+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]; } //cout<<"haja\n"; // q=1; while(q--){ ll x,y; cin>>x>>y; memset(dp,-1,sizeof(dp)); x--;y--; // cout<<x<<" "<<y<<"\n"; cout<<solve(x,y,4)<<"\n"; } } return 0; } /* 1 3 3 5 3 2 6 1 4 5 3 1 1 1 1 2 2 2 3 3 */
#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...