Submission #779631

#TimeUsernameProblemLanguageResultExecution timeMemory
779631Ahmed57Abduction 2 (JOI17_abduction2)C++17
27 / 100
3048 ms128436 KiB
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3") #include <bits/stdc++.h> using namespace std; //dir = 0 left //dir = 1 right //dir = 2 up //dir = 3 down int dp[2001][2001][4]; int n,m,q; int arr1[2001],arr2[10001]; int solve(int x,int y,int dir){ if(x<0||x>=n||y<0||y>=m)return -1; if(dp[x][y][dir]!=-1)return dp[x][y][dir]; if(dir==0){ if(arr2[y]>arr1[x]){ int c1 = 0; c1 = max(c1,solve(x-1,y,2)+1); c1 = max(c1,solve(x+1,y,3)+1); return dp[x][y][dir] = c1; }else{ return dp[x][y][dir] = solve(x,y-1,dir)+1; } }if(dir==1){ if(arr2[y]>arr1[x]){ int c1 = 0; c1 = max(c1,solve(x-1,y,2)+1); c1 = max(c1,solve(x+1,y,3)+1); return dp[x][y][dir] = c1; }else{ return dp[x][y][dir] = solve(x,y+1,dir)+1; } }if(dir==2){ if(arr1[x]>arr2[y]){ int c1 = 0; c1 = max(c1,solve(x,y-1,0)+1); c1 = max(c1,solve(x,y+1,1)+1); return dp[x][y][dir] = c1; }else{ return dp[x][y][dir] = solve(x-1,y,dir)+1; } }if(dir==3){ if(arr1[x]>arr2[y]){ int c1 = 0; c1 = max(c1,solve(x,y-1,0)+1); c1 = max(c1,solve(x,y+1,1)+1); return dp[x][y][dir] = c1; }else{ return dp[x][y][dir] = solve(x+1,y,dir)+1; } } } int main(){ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); cin>>n>>m>>q; for(int i = 0;i<n;i++)cin>>arr1[i]; for(int i = 0;i<m;i++)cin>>arr2[i]; memset(dp,-1,sizeof dp); while(q--){ int a,b;cin>>a>>b; a--;b--; int ans = 0; ans = max(ans,solve(a,b-1,0)+1); ans = max(ans,solve(a,b+1,1)+1); ans = max(ans,solve(a-1,b,2)+1); ans = max(ans,solve(a+1,b,3)+1); cout<<ans<<"\n"; } }

Compilation message (stderr)

abduction2.cpp: In function 'int solve(int, int, int)':
abduction2.cpp:52:1: warning: control reaches end of non-void function [-Wreturn-type]
   52 | }
      | ^
#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...